Submission #724447

#	Time	Username	Problem	Language	Result	Execution time	Memory
724447		rt144	Bridges (APIO19_bridges)	C++17	100 / 100	1763 ms	11244 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+5, maxm = 1e5+5;
int n, m, q, ans[maxm];
struct edge { int u, v, w; } es[maxm];
struct upd { int isu, t, x, y; };
struct DSU {
	int p[maxn], sz[maxn];
	stack<int> h;
	DSU() { iota(p, p+n+1, 0); fill(sz, sz+n+1, 1); }
	int get(int x) { while(p[x]!=x) x=p[x]; return x; }
	bool merge(int x, int y, bool rec) {
		int a = get(x), b = get(y);
		if (a==b) return false;
		if (sz[b]>sz[a]) swap(a, b);
		sz[a] += sz[b]; p[b] = a;
		if (rec) h.push(b);
		return true;
	}
	void rollback(int t) {
		while (h.size()>t) {
			int b = h.top(); h.pop();
			sz[p[b]] -= sz[b];
			p[b] = b;
		}
	}
};

int32_t main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m; const int B = 1000;
	for (int i=1;i<=m;i++) cin >> es[i].u >> es[i].v >> es[i].w;
	int q; cin >> q; vector<upd> qs(q);
	for (int i=0;i<q;i++) cin >> qs[i].isu >> qs[i].x >> qs[i].y, qs[i].t=i;
	for (int b=0;b<q;b+=B) {
		int bsz = min(q-b, B);
		bitset<maxm> isch = 0ull;
		vector<upd> ch, qu;
		for (int i=b;i<b+bsz;i++) {
			if (qs[i].isu==1) isch[qs[i].x]=1, ch.push_back(qs[i]);
			else qu.push_back(qs[i]);
		}
		vector<edge> un; for (int i=1;i<=m;i++) if (!isch[i]) un.push_back(es[i]);
		sort(begin(un), end(un), [](edge a, edge b) { return a.w<b.w; });
		sort(begin(qu), end(qu), [](upd a, upd b) { return a.y>b.y; });
		vector<vector<int>> to_merge(bsz);
		for (int i=b;i<b+bsz;i++) {
			if (qs[i].isu==1) es[qs[i].x].w = qs[i].y;
			else for (auto [_,ct,bi,_1]:ch) if (es[bi].w>=qs[i].y) to_merge[i-b].push_back(bi);
		}
		DSU dsu;
		for (auto [_, t, s, cw] : qu) {
			while (!un.empty() && un.back().w>=cw) {
				auto [u, v, _] = un.back();
				dsu.merge(u, v, false); un.pop_back();
			}
			int pt = dsu.h.size();
			for (int j : to_merge[t-b])
				dsu.merge(es[j].u, es[j].v, true);
			ans[t] = dsu.sz[dsu.get(s)];
			dsu.rollback(pt);
		}
	}
	for (int i=0;i<q;i++) if (ans[i]) cout << ans[i] << '\n';
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::rollback(int)':
bridges.cpp:21:18: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |   while (h.size()>t) {
      |          ~~~~~~~~^~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27