https://agc002.contest.atcoder.jp/tasks/agc002_d
永続unionfindかぁと思ってたけど、想定解は並列二分探索というものらしいです。
同じような二分探索を大量にしないと行けない時に、まとめてやる感じです。
辺の数と点の数をswapしていて無限にバグらせた…
struct query { int a, b, c; }; int N, M, Q, E; query T[MAX_N]; int ans[MAX_N]; struct edge { int u, v, cost; }; edge es[MAX_N]; vector<pi> iv[40]; vector<vi> iq[40]; void sub_solve() { iv[0].resize(1); iv[0][0] = pi(-1, M - 1); iq[0].resize(1); iq[0][0].resize(Q); rep(i, 0, Q) iq[0][0][i] = i; int at = 0; while(true) { // debug(iv[at]); // debug(iq[at]); int n = sz(iv[at]); int iqat = 0; vector<pi> quexe; rep(i, 0, n) { if(iv[at][i].sec - iv[at][i].fst == 1) { rep(j, 0, sz(iq[at][i])) { ans[iq[at][i][j]] = iv[at][i].sec; } } else quexe.pb(pi((iv[at][i].fst + iv[at][i].sec) / 2, i)); } // debug(quexe); if(sz(quexe) == 0) return; iv[at + 1].resize(sz(quexe) * 2); iq[at + 1].resize(sz(quexe) * 2); UF uf(N); rep(i, 0, M) { edge e = es[i]; if(!uf.same(e.u, e.v)) { uf.unite(e.u, e.v); } if(iqat < sz(quexe) && quexe[iqat].fst == i) { pi p = quexe[iqat]; vector<int>& vec = iq[at][p.sec]; int l = iqat * 2, r = iqat * 2 + 1; iv[at + 1][l] = pi(iv[at][p.sec].fst, p.fst); iv[at + 1][r] = pi(p.fst, iv[at][p.sec].sec); rep(i, 0, sz(vec)) { query t = T[vec[i]]; int tmp; if(!uf.same(t.a, t.b)) { tmp = uf.get_size(t.a) + uf.get_size(t.b); } else { tmp = uf.get_size(t.a); } if(tmp >= t.c) iq[at + 1][l].pb(vec[i]); else iq[at + 1][r].pb(vec[i]); } iqat++; } } at++; } }