Submission #724438

#	Time	Username	Problem	Language	Result	Execution time	Memory
724438		rt144	Bridges (APIO19_bridges)	C++17	14 / 100	1165 ms	10716 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
// #define int int64_t
const int maxn = 5e4+5, maxm = 1e5+5, inf = 1e9+10;
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]; // edge weight to parent
	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; }
	// int size(int x) { return sz[get(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); //fill(ans, ans+q+1, -1);
	for (int i=0;i<q;i++) cin >> qs[i].isu >> qs[i].x >> qs[i].y, qs[i].t=i;
	// IC(B, qs);
	for (int b=0;b<q;b+=B) {
		// int bsz = min(q-b, B);
		// vector<bool> isch(m+1, false);
		bitset<maxm> isch = 0ull;
		vector<upd> ch, qu;
		for (int i=b;i<b+B&&i<q;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; });
		// sort(begin(ch), end(ch), [](upd a, upd b) { return a.y>b.y; });
		// IC(un, qu, ch);
		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 (auto [_,ct,b,r] : ch) if ((t>ct && r>=cw)||(t<ct && es[b].w>=cw)) {
				dsu.merge(es[b].u, es[b].v, true);
				// else
			}
			ans[t] = dsu.sz[dsu.get(s)];
			dsu.rollback(pt);
			// IC(t, s, w, ans[t]);
		}
		for (auto [_,ct,b,r] : ch) es[b].w = r;
	}
	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:23:18: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |   while (h.size()>t) {
      |          ~~~~~~~~^~

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