AGC002D: Stamp Rally

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++;
	}
}