TopCoder SRM 618 Div1 Easy Family [1人競技プログラミング Advent Calendar 2016 17日目]

色々あって時間が取れなかったのと今日も時間が無いので手短に…。

この記事は1人競技プログラミング Advent Calendar 2016 17日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement

解いた方法：
親同士に辺を貼ったグラフが2色で塗れるかどうかをDFS

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

vector<VI> G;
VI color;

void add_edge(int from, int to){
    G[from].PB(to);
    G[to].PB(from);
}

bool dfs(int now, int c){
    if(color[now] != c && color[now] != 0) return false;
    if(color[now] != 0) return true;

    color[now] = c;
    REP(i, G[now].size()){
        if(!dfs(G[now][i], c*-1)){
            return false;
        }
    }

    return true;
}

class Family {
    public:
    vector<int> parent1;
    vector<int> parent2;
    string isFamily(vector<int> _parent1, vector<int> _parent2) {
        parent1 = _parent1, parent2 = _parent2;

        G.clear();
        color.clear();
        REP(i, parent1.size()){
            VI tmp;
            G.PB(tmp);
            color.PB(0);
        }

        REP(i, parent1.size()){
            if(parent1[i] == -1) continue;

            add_edge(parent1[i], parent2[i]);
        }

        REP(i, parent1.size()){
            if(color[i] == 0){
                if(!dfs(i,1)){
                    return "Impossible";
                }
            }
        }

        return "Possible";
    }
};