CODE FESTIVAL 2017 qual B C. 3 Steps

CODE FESTIVAL 2017 qual B C. 3 Steps

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

感想

qual Aには出れなかったので、qual Bから参戦していた。40分で3完し、そのあとはひたすらDのバグをつぶそうとしていた。

総合243位、日本人98位なので本戦には行けないが、得意な感じの問題がCで出てくれたのでパフォーマンスは悪くなかった。そのCについて解法をまとめておく。

解法

移動をスタートする頂点を$\ S\ $に固定して考える。まず頂点$\ S\ $には$\ 0\ $と書き、$\ S\ $から進んだ距離を各頂点に書いていくことにする。ただし、$\ 2\ $と書いた次の頂点には、$\ 1\ $と書くことにする（つまり交互に書く）。なぜなら、本来$\ 3\ $と書かれるべき頂点には、$\ S\ $から辺を張れるので、それは$\ 1\ $とみなせるからである。すると、$\ S\ $を除くすべての頂点が$\ 1\ $または$\ 2\ $で塗られることになる。ただし、これは少し嘘で、塗り方に矛盾が生まれる場合があって、それは奇閉路が存在するときに限る。$\ 1\ $と書かれた頂点には辺を張ることが可能であり、$\ 2\ $と書かれた頂点には辺を張ることが不可能である。先に述べたように、奇閉路があるときは、すべての頂点を$\ 1\ $で塗れるので、すべての頂点に辺を張ることが可能である。
グダグダ書いたが結局二部グラフかどうかを見て、適当に完全グラフまたは二部グラフを作って辺を数えればよい。$\ O(n)\ $。答えは最大$\ 10^{10}\ $程度にまで大きくなるのでオーバーフローに気をつけること。

実装

#include "bits/stdc++.h"
using namespace std;

void dfs(int v, int prev, int color, vector<int> &used, vector<vector<int>> &g, bool &can) {
        used[v] = color;
        for (auto u : g[v]) if (u != prev) {
                if (used[u] == -1) dfs(u, v, 1 - color, used, g, can);
                else if (used[u] != 1 - color) can = true;
        }
}

int main() {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        vector<int> used(n, -1);
        bool can = false;
        dfs(0, -1, 0, used, g, can);
        long long ans;
        if (can) ans = (long long) n * (n - 1) / 2;
        else {
                int black = 0;
                for (int i = 0; i < n; i ++) black += used[i];
                ans = (long long) black * (n - black);
        }
        cout << ans - m << endl;
        return 0;
}