Submission #545950

#	Time	Username	Problem	Language	Result	Execution time	Memory
545950		amunduzbaev	Bridges (APIO19_bridges)	C++17	100 / 100	2280 ms	10028 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];
 
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];
	
	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]--;
	}
	
	vector<int> p(m); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return e[i][2] > e[j][2];
	});	
	
	for(int b=0;b * B<Q;b++){
		//~ cout<<"here"<<endl;
		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);
			}
		}
		
		sort(tt.begin(), tt.end()); tt.erase(unique(tt.begin(), tt.end()), tt.end());
		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(int k=l;k<r;k++){
			if(q[k][0] == 1){
				e[q[k][1]][2] = q[k][2];
			}
		}
		{
			vector<int> tmp;
			sort(tt.begin(), tt.end(), [&](int i, int j){
				return (e[i][2] > e[j][2]);
			});
			
			int l = 0, r = 0;
			while(l < m || r < (int)tt.size()){
				while(l < m && used[p[l]]) l++;
				if(l < m && r < (int)tt.size()){
					if(e[p[l]][2] > e[tt[r]][2]){
						tmp.push_back(p[l++]);
					} else {
						tmp.push_back(tt[r++]);
					}
				} else if(l < m){
					tmp.push_back(p[l++]);
				} else if(r < (int)tt.size()){
					tmp.push_back(tt[r++]);
				}
			}
			
			swap(p, tmp);
			//~ vector<int> t(m); iota(t.begin(), t.end(), 0);
			//~ sort(t.begin(), t.end(), [&](int i, int j){
				//~ return (e[i][2] > e[j][2]);
			//~ });
			
			//~ for(auto x : t) cout<<x<<" ";
			//~ cout<<endl;
			//~ for(auto x : p) cout<<x<<" ";
			//~ cout<<endl;
		}
		
		for(auto x : tt) used[x] = 0;
	}
	
	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: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27