제출 #545875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545875		amunduzbaev	다리 (APIO19_bridges)	C++17	16 / 100	3050 ms	4820 KiB

bridges

#include "bits/stdc++.h"
using namespace std;

#define ar array
const int B = 320;

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);
	
	for(int b=0;b * B<Q;b++){
		vector<int> par(n + 1), sz(n + 1, 1);
		iota(par.begin(), par.end(), 0);
		
		//~ 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];
		//~ };
		
		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});
		};
		
		int l = b * B, r = min(Q, (b + 1) * B);
		vector<int> used(m), uu(m), 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(p.begin(), p.end(), [&](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){
			while(j<m && e[p[j]][2] >= q[i][2]){
				if(!used[p[j]]){
					fmerge(e[p[j]][0], e[p[j]][1], 0);
				} j++;
			}
			
			for(int j=i-1;j>=l;j--){
				if(q[j][0] != 1 || uu[q[j][1]]) continue;
				uu[q[j][1]] = 1;
				if(q[j][2] >= q[i][2]){
					fmerge(e[q[j][1]][0], e[q[j][1]][1], 1);
				}
			}
			
			for(auto x : tt){
				if(uu[x]) { uu[x] = 0; continue; }
				if(e[x][2] >= q[i][2]){
					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 j=l;j<r;j++){
			if(q[j][0] == 1){
				e[q[j][1]][2] = q[j][2];
			}
		}
	}
	
	for(int i=0;i<Q;i++){
		if(q[i][0] == 2) cout<<res[i]<<"\n";
	} cout<<"\n";
}

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