Atcoder AGC 005 E. Sugigma: The Showdown

Atcoder AGC 005 E. Sugigma: The Showdown

E: Sugigma: The Showdown - AtCoder Grand Contest 005 | AtCoder

感想

後半の考察に1時間以上かかったが、自力で一発ACしたので嬉しかった。木とゲームに関する問題はやっぱり得意だ。

解法

以下、先手を$\ N\ $、後手を$\ P\ $と呼ぶことにする。

まずゲームが終了しない場合というのはどういう場合なのかを考察する。無限にループが起こる部分というのは、$\ N\ $にとっては距離$\ 1\ $であってかつ、$\ P\ $にとっては距離$\ 3\ $以上であるような2頂点間である。これは図を書けば簡単に証明できる。このようなループに$\ N\ $が$\ P\ $に追いつかれないように到達できるならばゲームは終了しないことがわかる。

このようなループを含む点を列挙するには、まず$\ N\ $に関する木の隣り合う頂点をペアにして保管しておき、そのそれぞれに対して$\ P\ $に関する木の上での距離が求められれば良い。これは$\ P\ $に関する根付き木のLCAを考えて、はい。

さて、あとは$\ N\ $が$\ P\ $と出会わない範囲でどのような移動ができるのかを考えればよい。よく考えると、$\ P\ $は$\ P\ $に関する木の上を（ループを考慮しなければ）どんどん下に向かって($\ N\ $に向かって）下りていくという戦法しか取る必要がない。すると、$\ P\ $に関する木においてそのdepthがそのまま$\ P\ $が到達するのに必要なステップ数に一致する。

よって、移動しようとしている点について、$\ P\ $が到達するステップ数より自身のステップ数が小さいような移動のみを行なっていけば良い。これは典型的な$\ BFS\ $を記述すればよい。

$\ BFS\ $の途中で、ループを含むような点に到達できたなら、ゲームは終了しないので-1を出力する。そうでないなら通ることができたすべての点についてdepthの最大値をとれば、$\ P\ $がゲームを終わらせるためのステップ数の最大値が求められるので、ターン数としてその2倍を出力する。

実装

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

#define pii pair<int, int>

struct state { int v, step; };

vector<int> gx[202020];
vector<int> gy[202020];
int depth[202020];
int parent[30][202020];

void dfs(int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (auto i : gy[v]) if (i != p) dfs(i, v, d + 1);
}
void init(int s, int V) {
        dfs(s, -1, 0);
        for (int k = 0; k < 30 - 1; k ++) {
                for (int i = 0; i < V; i ++) {
                        if (parent[k][i] < 0) parent[k + 1][i] = -1;
                        else parent[k + 1][i] = parent[k][parent[k][i]];
                }
        }
}
int lca(int u, int v) { 
        if (depth[u] > depth[v]) swap(u, v);
        for (int k = 0; k < 30; k ++) {
                if ((depth[v] - depth[u]) >> k & 1) { 
                        v = parent[k][v];
                }
        }
        if (u == v) return u;
        for (int k = 30 - 1; k >= 0; k --) {
                if (parent[k][u] != parent[k][v]) {
                        u = parent[k][u];
                        v = parent[k][v];
                }
        }
        return parent[0][u];
}
int dist(int u, int v) {
        return depth[u] + depth[v] - depth[lca(u, v)] * 2;
}

int main() {
        int n, x, y;
        cin >> n >> x >> y;
        x --, y --;
        vector<pii> edge(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                edge[i] = mp(a, b);
                gx[a].push_back(b);
                gx[b].push_back(a);
        }
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                gy[a].push_back(b);
                gy[b].push_back(a);
        }
        init(y, n);
        vector<pii> loop;
        for (int i = 0; i < n - 1; i ++) {
                if (dist(edge[i].first, edge[i].second) >= 3) loop.push_back(edge[i]);
        }
        set<int> loop_set;
        for (int i = 0; i < loop.size(); i ++) {
                loop_set.insert(loop[i].first);
                loop_set.insert(loop[i].second);
        }
        queue<state> q;
        q.push((state){ x, 0 });
        int ans = -1;
        vector<bool> used(n, false);
        used[x] = true;
        while (!q.empty()) {
                state now = q.front(); q.pop();
                ans = max(ans, depth[now.v] * 2);
                if (loop_set.count(now.v)) {
                        cout << -1 << endl;
                        return 0;
                }
                for (auto next : gx[now.v]) if (!used[next]) {
                        used[next] = true;
                        if (depth[next] <= now.step + 1) continue;
                        q.push((state){ next, now.step + 1 });
                }
        }
        cout << ans << endl;
        return 0;
}