Balancing Network [AtCoder Grand Contest 041 E]

https://atcoder.jp/contests/agc041/tasks/agc041_e

前提知識

• bitset高速化

解説

https://atcoder.jp/contests/agc041/submissions/9195266

2つの問題が入っているが、全く別のアプローチで解く。

T=1では、bitset高速化で解く。
dp[i][j] := 平衡器iから平衡器jへ到達可能か
これのjの部分をbitsetで持つことにする。
すると、X[i]とY[i]のケーブルによって、
dp[X[i]] = dp[Y[i]] = dp[X[i]] | dp[Y[i]]
と更新することができる。
これで、dp[i]でbitが立っている個数がNであるものがあれば、そこにコインを集めることができる。
復元パートは、逆からUnionFindを使って、集める目的地へ向かって矢印を伸ばせばいい。

T=2を考えよう。
一番難しいパターンを考えてみる。
N=2はどう抗っても無理そう。なので-1。
N=3はどうだろう。
M=100000としても解けるだろうか。
実は解ける。
M[i]に↑か↓をつけるが、矢印の先の平衡器がM[i+1]のケーブルの端点になっていない方を選ぶ。
これだけで実は達成できる。
一般化すると、途中までは適当に矢印をつけて、3つの平衡器になったら、その段階でさきのアルゴリズムを適用する。

でも、これは実装が結構大変なので、答えに書いてあるcntとBを使う解法が実装が軽くてオススメ。
なんで、それでうまくいくのかはよくわからん。

int N, M, T;
int X[101010], Y[101010];
#define UP '^'
#define DOWN 'v'
//---------------------------------------------------------------------------------------------------
using BS = bitset<50101>;
BS dp[50101];
void solve1() {
    rep(i, 0, N) dp[i].set(i);

    rep(i, 0, M) dp[X[i]] = dp[Y[i]] = dp[X[i]] | dp[Y[i]];
    rep(i, 0, N) if (dp[i].count() == N) {
        int goal = i;
        UnionFind uf(N);
        string ans = "";
        rrep(j, M - 1, 0) {
            int g = uf[goal];
            int x = uf[X[j]];
            int y = uf[Y[j]];

            if (g != x and g != y) ans += UP;
            else if (g == x and g == y) ans += UP;
            else if (g == x) {
                ans += UP;
                uf(x, y);
            }
            else {
                ans += DOWN;
                uf(x, y);
            }
        }
        reverse(all(ans));
        cout << ans << endl;
        return;
    }

    cout << -1 << endl;
}
//---------------------------------------------------------------------------------------------------
int B[50101], cnt[50101];
void solve2() {
    if (N == 2) {
        cout << -1 << endl;
        return;
    }

    rep(i, 0, N) B[i] = i, cnt[i] = 1;

    string ans = "";
    rrep(i, M - 1, 0) {
        int x = X[i], y = Y[i];
        int bx = B[x], by = B[y];

        if (cnt[bx] > cnt[by]) {
            ans += DOWN;
            cnt[by]++;
            cnt[bx]--;
            B[x] = by;
        }
        else {
            ans += UP;
            cnt[bx]++;
            cnt[by]--;
            B[y] = bx;
        }
    }
    reverse(all(ans));
    cout << ans << endl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> T;
    rep(i, 0, M) {
        cin >> X[i] >> Y[i];
        X[i]--, Y[i]--;
    }

    if (T == 1) solve1();
    else solve2();
}