Submission #559670

#	Time	Username	Problem	Language	Result	Execution time	Memory
559670		heavylightdecomp	Bridges (APIO19_bridges)	C++14	0 / 100	3069 ms	10344 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int mxN = 5e4+5, mxM = 1e5+5, bsz = 320;
struct dsu {
	int n;
	int par[mxN], ccsz[mxN], hu[bsz*mxM], hv[bsz*mxM], 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; hu[hsz] = u, hv[hsz] = v;
	}
	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) {
		assert(to <= hsz);
		while(hsz > to) {
			int u = hu[hsz], v = hv[hsz];
			par[u] = u; ccsz[v] -= ccsz[u];
			--hsz;
		}
	}
} D;
tuple<int,int,int> edges[mxM];
set<tuple<int,int,int,int>> est;
tuple<int,int,int> ops[mxM];
int ans[mxM];
bool requested[mxM];
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++) {
		int u, v, d; cin >> u >> v >> d;
		edges[i] = {d,u,v};
		est.insert({d,u,v,i});
	}
	D.prep(n);
	int q; cin >> q;
	for(int g = 1; g <= q; g++) {
		int t; cin >> t;
		if(t==1) {
			int b, r; cin >> b >> r;
			ops[g] = {0,b,r};
		} else {
			int s, w; cin >> s >> w;
			ops[g] = {1,s,w};
			requested[g] = true;
		}
	}

	for(int i = 1; i <= q;) {
		int ben = min(i+bsz-1, q);
		vector<tuple<int,int,int>> upds; //{#id, edge, weight}
		vector<tuple<int,int,int>> asks;
		while(i <= ben) {
			int t, a, b; tie(t,a,b) = ops[i];
			if(t==0) {
				upds.push_back({i,a,b});
			} else {
				asks.push_back({b,a,i});
			}
			i++;
		}
		sort(asks.begin(), asks.end());
		vector<tuple<int,int,int,int>> restore;
		for(auto changed : upds) {
			int eid = get<1>(changed);
			tuple<int,int,int,int> old = {get<0>(edges[eid]), get<1>(edges[eid]), get<2>(edges[eid]), eid};
			est.erase(old);
			restore.push_back(old);
		}
		
		if(asks.size()) {
			if(est.size()) {
				auto j = prev(est.end());
				int beforeblock = D.hsz;
				for(int c = asks.size()-1; c >= 0; c--) {
					int w, s, oid; tie(w,s,oid) = asks[c]; bool done = false;
					while(!done && get<0>(*j) >= w) {
						D.merge(get<1>(*j), get<2>(*j));
						if(j == est.begin()) { done = 1; break; }
						--j;
					}
					int before = D.hsz;
					//cerr << get<0>(upds[0]) << endl;
					for(int pend = 0; pend < upds.size(); pend++) {
						if((get<0>(upds[pend])) < oid) {
						if(get<2>(upds[pend]) >= w) {
							int eid = get<1>(upds[pend]);
							int u = get<1>(edges[eid]), v = get<2>(edges[eid]);
							//cerr << "q " << oid << " merge " << u << ' ' << v << endl;
							D.merge(u,v);
						}
						} else {
							int eid = get<1>(upds[pend]);
							int oldweight = get<0>(edges[eid]);
							if(oldweight >= w) {
								int u = get<1>(edges[eid]), v = get<2>(edges[eid]);
								D.merge(u,v);
							}
						}
					}
					ans[oid] = D.ccsz[D.find(s)];
					D.rollback(before);
				}
				D.rollback(beforeblock);
			}
		}
		for(auto gone : restore) {
			est.insert(gone);
		}
		for(auto it : upds) {
			int qid, b, r;
			tie(qid, b, r) = it;
			int u = get<1>(edges[b]), v = get<2>(edges[b]), prevd = get<0>(edges[b]);
			est.erase({prevd,u,v,b});
			edges[b] = {r,u,v};
			est.insert({r,u,v,b});
		}
	}

	for(int i = 1; i <= q; i++) if(requested[i]) cout << ans[i] << '\n';
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:92:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |      for(int pend = 0; pend < upds.size(); pend++) {
      |                        ~~~~~^~~~~~~~~~~~~

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