Submission #559725

#	Time	Username	Problem	Language	Result	Execution time	Memory
559725		heavylightdecomp	Bridges (APIO19_bridges)	C++14	100 / 100	2817 ms	170108 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
const int mxN = 1e5+5, bsz = 1024;
struct dsu {
	int n;
	int par[mxN], ccsz[mxN], h[bsz*mxN], hsz;
	void prep(int _n) {n = _n; for(int i = 1; i <= n; i++) par[i] = i, ccsz[i] = 1; }
	int find(int x) { while(par[x]!=x) x = par[x]; return x; }
	inline void push(int u, int v) {++hsz; h[hsz] = u;}
	void merge(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(ccsz[a] > ccsz[b]) swap(a,b);
		push(a,b);
		par[a] = b;
		ccsz[b] += ccsz[a];
	}
	void rollback(int to) {
		while(hsz > to) { ccsz[par[h[hsz]]] -= ccsz[h[hsz]]; par[h[hsz]] = h[hsz]; --hsz;}
	}
} D;

int ans[mxN], u[mxN], v[mxN], d[mxN], t[mxN], p[mxN], w[mxN], c[mxN];
vector<int> good[mxN];
signed main() {
	//freopen("bridge.in", "r", stdin);
	//freopen("bridge.out", "w", stdout);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> d[i];
	int q; cin >> q;
	for(int i = 1; i <= q; i++) cin >> t[i] >> p[i] >> w[i];
	for(int l = 1; l <= q; l += bsz) {
		int r = min(l+bsz-1,q);
		iota(D.par+1, D.par+mxN, 1);
		memset(c, 0, sizeof c);
		for(int i = 0; i < mxN; i++) D.ccsz[i] = 1;
		vector<int> ask, upd, same, bad;
		for(int i = l; i <= r; i++) if(t[i]==1) c[p[i]]=1; else ask.push_back(i);
		for(int i = 1; i <= m; i++) { if(!c[i]) same.push_back(i); else bad.push_back(i); }
		for(int i = l; i <= r; i++) {
			if(t[i]==1) d[p[i]] = w[i]; else for(int cand : bad) if(d[cand] >= w[i]) good[i].push_back(cand);
		}
		sort(begin(same), end(same), [&](int a, int b) { return d[a] > d[b]; });
		sort(begin(ask), end(ask), [&](int a, int b) { return w[a] > w[b]; });
		int fbe = 0;
		const int ssz = same.size();
		for(int query : ask) {
			while(fbe < ssz && d[same[fbe]] >= w[query]) D.merge(u[same[fbe]], v[same[fbe]]), fbe++;
			int before = D.hsz;
			for(int also : good[query]) D.merge(u[also], v[also]);
			ans[query] = D.ccsz[D.find(p[query])];
			D.rollback(before); 
		}
	}
	for(int i = 1; i <= q; i++) if(t[i]==2) cout << ans[i] << '\n';
}

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