Submission #404127

#	Time	Username	Problem	Language	Result	Execution time	Memory
404127		thomas_li	Bridges (APIO19_bridges)	C++17	30 / 100	3091 ms	146296 KiB

bridges

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int MM = 5e4+5,SZ = 1e3;

struct DSU{
	struct op{
		int u,su,v,sv;
	};
	stack<op> ev;
	vector<int> p, sz;
	DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(),0); }
	void clear(){
		for(int i = 0; i < p.size(); i++) p[i] = i, sz[i] = 1;
	}
	// no path compression due to undo operation
	int find(int u) { return u == p[u] ? u : find(p[u]); }
	void join(int u, int v){
		u = find(u); v = find(v);
		if(sz[u] > sz[v]) swap(u,v);
		ev.push({u,sz[u], v,sz[v]});
		if(u == v) return;
		sz[v] += sz[u];
		p[u] = v;
	}
	void undo(){
		op e = ev.top(); ev.pop();
		sz[e.u] = e.su; sz[e.v] = e.sv; 
		p[e.u] = e.u; p[e.v] = e.v;
	}
	int get_size(int u) { return sz[find(u)]; } 
	bool same_set(int u, int v) { return find(u) == find(v); }
};
vector<int> ext[SZ];
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n,m,q; cin >> n >> m; vector<array<int,3>> el,qu; 
	for(int i = 0; i < m; i++){
		int u,v,w; cin >> u >> v >> w; u--; v--;
		el.push_back({u,v,w});
	}
	cin >> q;
	vector<int> ans(q);
	for(int i = 0; i < q; i++){
		int t,a,b; cin >> t >> a >> b;
		a--;
		qu.push_back({t,a,b});
	}
	DSU d(n); bitset<MM*2> mod;
	for(int l = 0; l < q; l += SZ){
		d.clear(); mod.reset();
		int r = min(q-1,l+SZ-1);
		vector<int> cur_u,cur_q,old;
		for(int i = l; i <= r; i++){
			auto[t,a,b] = qu[i];
			if(t == 1){
				mod[a] = 1;
				cur_u.emplace_back(i);
			} else{
				cur_q.emplace_back(i);
			}
		}
		for(int i = 0; i < m; i++){
			if(!mod[i]) old.emplace_back(i);
		}
		for(int i = l; i <= r; i++){
			auto[t,a,b] = qu[i];
			if(t == 1){
				auto&[u,v,w] = el[a];
				w = b;
			} else{
				ext[i-l].clear();
				for(int x : cur_u){
					if(el[qu[x][1]][2] >= b){
						ext[i-l].emplace_back(qu[x][1]);
					}
				}
			}
		}
		sort(old.begin(),old.end(),[&](const auto& ls, const auto& rs){
			return el[ls][2] > el[rs][2];
		});
		sort(cur_q.begin(),cur_q.end(),[&](const auto& ls, const auto& rs){
			return qu[ls][2] > qu[rs][2];
		});
		int ptr = 0;
		for(int i = 0; i < (int)cur_q.size(); i++){
			while(ptr < (int)old.size() && el[old[ptr]][2] >= qu[cur_q[i]][2]){
				d.join(el[old[ptr]][0],el[old[ptr]][1]);
				ptr++;
			} 
			int cnt = 0;
			for(int x : ext[cur_q[i] - l]){
				d.join(el[x][0],el[x][1]); cnt++;
			}
			ans[cur_q[i]] = d.get_size(qu[cur_q[i]][1]);
			while(cnt--) d.undo();
		}
	}
	for(int i = 0; i < q; i++){
		if(qu[i][0] == 2) cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::clear()':
bridges.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0; i < p.size(); i++) p[i] = i, sz[i] = 1;
      |                  ~~^~~~~~~~~~

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