Submission #545921

#	Time	Username	Problem	Language	Result	Execution time	Memory
545921		amunduzbaev	Bridges (APIO19_bridges)	C++17	59 / 100	3086 ms	6004 KiB

bridges

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
const int B = 320;
const int N = 1e5 + 5;
int par[N], sz[N], used[N], uu[N], p[N];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<ar<int, 3>> e(m);
	for(int i=0;i<m;i++) cin>>e[i][0]>>e[i][1]>>e[i][2], p[i] = i;
	
	int Q; cin>>Q;
	vector<ar<int, 3>> q(Q);
	vector<int> res(Q);
	for(int i=0;i<Q;i++){
		cin>>q[i][0]>>q[i][1]>>q[i][2];
		if(q[i][0] == 1) q[i][1]--;
	}
	
	for(int b=0;b * B<Q;b++){
		for(int i=1;i<=n;i++) par[i] = i, sz[i] = 1;
		vector<ar<int, 2>> last;
 
		function<int(int)> ff = [&](int x) { return (par[x] == x ? x : ff(par[x])); };
		auto fmerge = [&](int a, int b, bool t){
			a = ff(a), b = ff(b);
			if(a == b) return;
			if(sz[a] < sz[b]) swap(a, b);
			par[b] = a, sz[a] += sz[b];
			if(t) last.push_back({a, b});
		};
		
		function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
		auto merge = [&](int a, int b){
			a = f(a), b = f(b);
			if(a == b) return;
			if(sz[a] < sz[b]) swap(a, b);
			par[b] = a, sz[a] += sz[b];
		};
		
		int l = b * B, r = min(Q, (b + 1) * B);
		vector<int> qq, tt;
		for(int i=l;i<r;i++){
			if(q[i][0] == 1){
				tt.push_back(q[i][1]);
				used[q[i][1]] = 1;
			} else {
				qq.push_back(i);
			}
		}
		{
			vector<int> tmp;
			for(auto x : tt){
				if(uu[x]) continue;
				uu[x] = 1, tmp.push_back(x);
			} swap(tt, tmp);
			for(auto x : tt) uu[x] = 0;
		}
		sort(p, p + m, [&](int i, int j){
			return e[i][2] > e[j][2];
		});
		
		sort(qq.begin(), qq.end(), [&](int i, int j){
			return (q[i][2] > q[j][2]);
		});
		
		int j=0;
		for(auto i : qq){ int w = q[i][2];
			while(j<m && e[p[j]][2] >= w){
				if(!used[p[j]]){
					merge(e[p[j]][0], e[p[j]][1]);
				} j++;
			}
			
			for(int k=i-1;k>=l;k--){
				if(q[k][0] != 1 || uu[q[k][1]]) continue;
				uu[q[k][1]] = 1;
				if(q[k][2] >= w){
					fmerge(e[q[k][1]][0], e[q[k][1]][1], 1);
				}
			}
			
			for(auto x : tt){
				if(uu[x]) { uu[x] = 0; continue; }
				if(e[x][2] >= w){
					fmerge(e[x][0], e[x][1], 1);
				}
			}
			
			res[i] = sz[ff(q[i][1])];
			while(!last.empty()){
				int a = last.back()[0], b = last.back()[1];
				sz[a] -= sz[b], par[b] = b;
				last.pop_back();
			}
		}
		
		for(auto x : tt) used[x] = 0;
		for(int k=l;k<r;k++){
			if(q[k][0] == 1){
				e[q[k][1]][2] = q[k][2];
			}
		}
	}
	
	for(int i=0;i<Q;i++){
		if(q[i][0] == 2) cout<<res[i]<<"\n";
	} cout<<"\n";
}

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