test/yukicoder/416.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://yukicoder.me/problems/no/416

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/416"
#include <bits/stdc++.h>

#include "library/datastructure/unionfind/PartialPersistentUnionFind.hpp"

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

    int n, m, q;
    std::cin >> n >> m >> q;
    PartialPersistentUnionFind uf(n);

    std::set<std::pair<int, int>> edge;
    while (m--) {
        int a, b;
        std::cin >> a >> b;
        a--;
        b--;
        edge.insert(std::minmax(a, b));
    }

    std::vector<std::pair<int, int>> query(q);
    for (int i = 0; i < q; i++) {
        int a, b;
        std::cin >> a >> b;
        a--;
        b--;
        edge.erase(std::minmax(a, b));
        query[i] = std::minmax(a, b);
    }

    for (const auto &[a, b] : edge)
        uf.merge(a, b);

    std::map<int, int> time;
    while (q--) {
        auto [a, b] = query[q];
        int now = uf.merge(a, b);
        time[now] = q + 1;
    }

    for (int i = 1; i < n; i++) {
        int t = uf.when_same(0, i);
        if (t == -1)
            std::cout << 0 << "\n";
        else if (!time.count(t))
            std::cout << -1 << "\n";
        else
            std::cout << time[t] << "\n";
    }
}

#line 1 "test/yukicoder/416.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/416"
#include <bits/stdc++.h>

#line 2 "library/datastructure/unionfind/PartialPersistentUnionFind.hpp"
// https://tiramister.net/blog/posts/persistent-unionfind/
class PartialPersistentUnionFind {
    int now; // 現在時刻
    std::vector<int> par, rank, time;
    std::vector<std::vector<std::pair<int, int>>> sz;
    static constexpr int NOW = std::numeric_limits<int>::max();

  public:
    PartialPersistentUnionFind(int n)
        : now(0), par(n), rank(n, 0), time(n, 0), sz(n) {
        std::iota(par.begin(), par.end(), 0);
    }

    // 時刻 t の leader
    int find(int x, int t = NOW) {
        while (x != par[x] and time[x] < t)
            x = par[x];
        return x;
    }
    // 時刻 t で x,y が連結か
    bool same(int x, int y, int t = NOW) { return find(x, t) == find(y, t); }
    // x と y がいつ連結になったか（まだ非連結なら -1 ）
    // stack を使う実装も考えたけど少し遅そう atcoder/submissions/37116694
    int when_same(int x, int y) {
        int diff = 0; // x の深さ - y の深さ
        int X = x, Y = y;
        while (par[x] != x) {
            x = par[x];
            diff++;
        }
        while (par[y] != y) {
            y = par[y];
            diff--;
        }
        if (x != y)
            return -1;
        int res = 0;
        while (X != Y) {
            if (diff > 0) {
                res = std::max(res, time[X]);
                X = par[X];
                diff--;
            } else {
                res = std::max(res, time[Y]);
                Y = par[Y];
                diff++;
            }
        }
        return res;
    }
    // merge が成功したら時刻を 1 進めたあとその時刻を返す
    // 失敗したら stop が false なら時刻を進めて、-1 を返す
    int merge(int x, int y, bool stop = false) {
        now++;
        x = find(x);
        y = find(y);
        if (x == y) {
            if (stop)
                now--;
            return -1;
        }
        if (rank[x] < rank[y])
            std::swap(x, y);
        sz[x].emplace_back(now, size(x) + size(y));
        if (rank[x] == rank[y])
            rank[x]++;
        par[y] = x;
        return time[y] = now;
    }
    // 時刻 t の連結成分 x のサイズ
    int size(int x, int t = NOW) {
        x = find(x, t);
        int ok = -1, ng = sz[x].size();
        while (ng - ok > 1) {
            int mid = (ok + ng) >> 1;
            (sz[x][mid].first <= t ? ok : ng) = mid;
        }
        return (~ok ? sz[x][ok].second : 1);
    }
};
#line 5 "test/yukicoder/416.test.cpp"

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

    int n, m, q;
    std::cin >> n >> m >> q;
    PartialPersistentUnionFind uf(n);

    std::set<std::pair<int, int>> edge;
    while (m--) {
        int a, b;
        std::cin >> a >> b;
        a--;
        b--;
        edge.insert(std::minmax(a, b));
    }

    std::vector<std::pair<int, int>> query(q);
    for (int i = 0; i < q; i++) {
        int a, b;
        std::cin >> a >> b;
        a--;
        b--;
        edge.erase(std::minmax(a, b));
        query[i] = std::minmax(a, b);
    }

    for (const auto &[a, b] : edge)
        uf.merge(a, b);

    std::map<int, int> time;
    while (q--) {
        auto [a, b] = query[q];
        int now = uf.merge(a, b);
        time[now] = q + 1;
    }

    for (int i = 1; i < n; i++) {
        int t = uf.when_same(0, i);
        if (t == -1)
            std::cout << 0 << "\n";
        else if (!time.count(t))
            std::cout << -1 << "\n";
        else
            std::cout << time[t] << "\n";
    }
}