引きこもり [技術室奥プログラミングコンテスト#4 Day2 E]

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_e

解説

https://atcoder.jp/contests/tkppc4-2/submissions/7035886

何から手をつけたものかと思うのだが、何か全探索対象か固定できるものを考える。
q[i]を固定してみると、操作がやりづらいが、Lを固定すると都合がいい。
Lを固定すると、C[i]≦Lを満たす辺が移動に使える。
この時、満たす辺を使って連結成分を考えたときに頂点数が最も少ない連結成分の頂点数が会える天使になる。
こういう事情を考えると、Lとして使う候補はC[i]に限られる。
なので、Lを全探索して、クエリで答える答えを前計算しておこう。
Lの候補を小さい方から見ていき、UnionFindを使って「連結→連結成分の最小値取得」をする。
連結成分の最小値取得は、multisetを使えばいい。

int N, M, Q, A[101010], B[101010];
ll C[101010];
ll ans[101010];
int sz[101010];
//---------------------------------------------------------------------------------------------------
multiset<int> ms;
void erase(int x) {
    auto ite = ms.find(x);
    ms.erase(ite);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    map<ll,vector<int>> edges;
    rep(i, 0, M) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--; B[i]--;
        edges[C[i]].push_back(i);
    }

    UnionFind uf(N);
    rep(i, 0, N) ms.insert(1);
    rep(i, 0, N) sz[i] = 1;
    rep(i, 0, 101010) ans[i] = -1;
    int pre = 1;
    ans[1] = 0;
    fore(p, edges) {
        ll L = p.first;
        auto v = p.second;

        fore(i, v) {
            int a = A[i];
            int b = B[i];

            if(uf[a] != uf[b]) {
                a = uf[a];
                b = uf[b];
                int sz2 = sz[a] + sz[b];
                erase(sz[a]);
                erase(sz[b]);
                uf(a, b);
                int ab = uf[a];
                sz[ab] = sz[a] + sz[b];
                ms.insert(sz[ab]);
            }
        }

        int mi = *ms.begin();
        while(pre < mi) {
            pre++;
            ans[pre] = L;
        }
    }

    rep(i, 0, Q) {
        int q; cin >> q;
        if(0 <= ans[q]) printf("%lld\n", ans[q]);
        else printf("trumpet\n");
    }
}