SRM 618 DIV1 Easy - Family (復習○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10541&rd=15851
・有効グラフが２つ与えられる。
・それぞれのグラフは親と子の関係を示しており、ｘ→ｙのときｘが親、ｙが子になる。
・子は親がいないか、２人の親がいるかのどちらかでなければならない。
・子のノード番号より、親のノード番号の方が小さくてはならない。
・２人親がいる場合は、１人が父親、１人が母親でなくてはならない。
・与えられたグラフが上記の条件を満たす場合は"Possible"、満たさない場合は
"Impossible"を返す。
解き方
・まず、子について親が０もしくは２人でないかを判定する。
・次に、ノード番号について規則通りかを判定する。
・次に、母親と父親とペアになるべきノードについて無向グラフを作成する。
・最後に、そのグラフについて母親もしくは父親を埋めていき、条件を満たすかどうか判定する。
→System Failed
・母親もしくは父親の埋め方がまずかった。
・最初はすべてのノードを順番に埋めていったが、これでは最適な埋め方にならない。
・最初に埋めていないノードを選択して父親か母親としたとき、それに連結したノードをBFSで調べていけばよい。
・反省：自分の書いたコードが正しいかのトレース不足だった。思いつきだけではなく
きちんと検証する癖をつける。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class Family {
public: string isFamily(vector<int> parent1, vector<int> parent2) {
int n=parent1.size();
FORE(i,0,n){
if(parent1[i]==-1 && parent2[i]!=-1)return "Impossible";
if(parent2[i]==-1 && parent1[i]!=-1)return "Impossible";
if(parent1[i]>=i || parent2[i]>=i)return "Impossible";
}
int d[n][n];
memset(d,0,sizeof(d));
FORE(i,0,n)if(parent1[i]!=-1){
d[parent1[i]][parent2[i]]=1;
d[parent2[i]][parent1[i]]=1;
}
int s[n];
memset(s,0,sizeof(s));
queue<int> q;
FORE(i,0,n)if(!s[i]){
q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
int cur=0;
FORE(i,0,n)if(d[x][i]){
if(s[i]==0)q.push(i);
cur|=s[i];
}
if(cur==3)return "Impossible";
else if(cur==1)s[x]=2;
else s[x]=1;
}
}
return "Possible";
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class Family {
public: string isFamily(vector<int> parent1, vector<int> parent2) {
int n=parent1.size();
FORE(i,0,n){
if(parent1[i]==-1 && parent2[i]!=-1)return "Impossible";
if(parent2[i]==-1 && parent1[i]!=-1)return "Impossible";
if(parent1[i]>=i || parent2[i]>=i)return "Impossible";
}
int d[n][n];
memset(d,0,sizeof(d));
FORE(i,0,n)if(parent1[i]!=-1){
d[parent1[i]][parent2[i]]=1;
d[parent2[i]][parent1[i]]=1;
}
int s[n];
memset(s,0,sizeof(s));
queue<int> q;
FORE(i,0,n)if(!s[i]){
q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
int cur=0;
FORE(i,0,n)if(d[x][i]){
if(s[i]==0)q.push(i);
cur|=s[i];
}
if(cur==3)return "Impossible";
else if(cur==1)s[x]=2;
else s[x]=1;
}
}
return "Possible";
}
};
int n;
int d[101][101],p[101];
class Family {
public:
bool dfs(int x,int parent){
FORE(i,0,n)if(d[x][i]){
if(p[i]==parent)return false;
if(p[i]==0){
p[i]=3-parent;
if(dfs(i,p[i])==false)return false;;
}
}
return true;
}
string isFamily(vector<int> parent1, vector<int> parent2) {
n=parent1.size();
memset(p,0,sizeof(p));
memset(d,0,sizeof(d));
FORE(i,0,n)if(parent1[i]!=-1){
d[parent1[i]][parent2[i]]=1;
d[parent2[i]][parent1[i]]=1;
}
FORE(i,0,n)FORE(j,0,n){
if(d[i][j] && p[i]==0){
p[i]=1;
if(!dfs(i,1))return "Impossible";
}
}
return "Possible";
}
};
int d[101][101],p[101];
class Family {
public:
bool dfs(int x,int parent){
FORE(i,0,n)if(d[x][i]){
if(p[i]==parent)return false;
if(p[i]==0){
p[i]=3-parent;
if(dfs(i,p[i])==false)return false;;
}
}
return true;
}
string isFamily(vector<int> parent1, vector<int> parent2) {
n=parent1.size();
memset(p,0,sizeof(p));
memset(d,0,sizeof(d));
FORE(i,0,n)if(parent1[i]!=-1){
d[parent1[i]][parent2[i]]=1;
d[parent2[i]][parent1[i]]=1;
}
FORE(i,0,n)FORE(j,0,n){
if(d[i][j] && p[i]==0){
p[i]=1;
if(!dfs(i,1))return "Impossible";
}
}
return "Possible";
}
};
