CodeFestival2015本戦 F問題 歩くピアニスト

CodeFestival本戦行ってきました…
んーなんというか、まぁ普通に本戦5問解いて、他も無難な感じで、実力相応という感じでした。
ただ、あんなにオタクたちが集まってる中で、みんな知り合いとしかしゃべろうとしませんよね。
"繋がる"とか言ってた割には知らない人との交流(強制)が少なかったので(Happy Hourとか言ってたけど、ん？という感じ)、もっと交流の場を設けて欲しかったなぁ。
そして何よりもスケジュールがパンパンでゆっくり出来ないのは残念だった。
Coderunnerだとお酒もあるし、テーブルごとにグループ分けて集まらせて懇親させ、人を変えてまたやったりなど、結構良かったなぁ。

なんてのはどうでもよくて、F解けませんでした。

解説を読めばわかります。
ただ気をつけるのは、NOのケースのときに辺を通る回数がマイナスになったりするので、それらを弾きましょう。
あと、自分はわざわざグラフ作ってdfsとかいうバカなことをしましたが、連結してるかどうかだけ知りたいんだったらUnionFindが頭良かったなーなんておもいました。

vector<int> G[7];
bool used[7];

int dfs(int v){
    used[v] = true;
    int sum = 1;
    for(int a : G[v]){
        if(!used[a]) sum+=dfs(a);
    }
    return sum;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll C[7];
    rep(i, 7) cin >> C[i];
    C[0]--;
    ll x = C[0]-C[6]+C[5]-C[4]+C[3]-C[2]+C[1];
    ll X[7];
    X[0] = x;
    for(int i=1; i<7; i++){
        X[i] = 2*C[i]-X[i-1];
    }
    bool ok = true;
    for(int i=0; i<7; i++){
        if(X[i] < 0) ok = false;
        if((X[i] + X[(i+1)%7])&1) ok = false;
    }
    for(int i=0; i<7; i++){
        if(X[(i+7-1)%7]) G[i].push_back((i+7-1)%7);
        if(X[(i+7)%7]) G[i].push_back((i+7+1)%7);
    }
    dfs(0);
    for(int i=0; i<7; i++){
        if(!used[i] && (X[(i+7-1)%7]+X[i])) ok = false;
    }
    cout << (ok ? "YES" : "NO") << endl;
}