제출 #389881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389881		Blagojce	다리 (APIO19_bridges)	C++11	100 / 100	2968 ms	25584 KiB

bridges

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 4e9;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t z;

const int mxn = 1e5;
const int bsz = 800;

int n, m, q;

int t[mxn], a[mxn], b[mxn];

int l[mxn], r[mxn], w[mxn];


int neww[mxn];
bool nonstat[mxn];


int link[mxn];
int siz[mxn];
int findx(int x){
	if(x == link[x]) return x;
	link[x] = findx(link[x]);
	return link[x];
}
void unite(int u, int v){
	u = findx(u);
	v = findx(v);
	
	if(u == v) return;
	
	if(siz[u] < siz[v]) swap(u, v);
	link[v] = u;
	siz[u] += siz[v];
}


vector<int> G[mxn];
bool vis[mxn];

int dfs(int u){
	vis[u] = true;
	int ret = siz[u];
	
	for(auto e : G[u]){
		if(!vis[e]){
			ret += dfs(e);
		}
	}
	return ret;
}

int ans[mxn];


void compress(){
	vector<pair<int,int> > v;
	fr(i, 0, m){
		v.pb({w[i], (i+1)});
	}
	fr(i, 0, q){
		v.pb({b[i], -i});
	}
	sort(all(v));
	
	int pr = -1;
	int val= -1;
	
	for(auto u : v){
		if(u.st != pr) ++val;
		if(u.nd > 0){
			w[u.nd-1] = val;
		}
		else{
			b[-u.nd] = val;
		}
		pr = u.st;
	}
}
vector<pair<int,int> > SOS[3*mxn];


void solve(){
	cin >> n >> m;
	fr(i, 0, m){
		cin >> l[i] >> r[i] >> w[i];
		--l[i];
		--r[i];
	}
	cin >> q;
	fr(i, 0, q){
		cin >> t[i] >> a[i] >> b[i];
		--a[i];
	}

	


	compress();
	
		
	vector<pair<int,int> > g;
	vector<int> v;
	
	fr(bi, 0, (q+bsz-1)/bsz){
		
		memset(nonstat, false, sizeof(nonstat));
		v.clear();
		g.clear();
		
		fr(i, 0, n){
			link[i] = i;
			siz[i] = 1;
		}
		
		
		fr(i, bi*bsz, min(q, (bi+1)*bsz)){
			if(t[i] == 1){
				nonstat[a[i]] = true;
			}
			else{
				SOS[b[i]].pb({1, i});
			}
		}
		fr(i, 0, m){
			if(!nonstat[i]){
				SOS[w[i]].pb({0, i});
			}
			else{
				v.pb(i);
			}
		}
		
		for(int i = q+m; i >= 0; i --){
			
			while(!SOS[i].empty()){
				g.pb(SOS[i].back());
				SOS[i].pop_back();
			}
			
		}
		
		
		
		
		//sort(all(g));
		for(auto u : g){
			if(u.st == 0){
				unite(l[u.nd], r[u.nd]);
			}
			else{
				for(auto edge : v) neww[edge] = -1;
				
				int pos = u.nd;

				fr(i, bi*bsz, min(q, (bi+1)*bsz)){
					if(t[i] != 1) continue;
					if(i < pos){
						neww[a[i]] = b[i];
					}
					else if(neww[a[i]] == -1){
						neww[a[i]] = w[a[i]];
					}
				}
				for(auto edge : v){
					if(neww[edge] >= b[pos]){
						int A = findx(l[edge]);
						int B = findx(r[edge]);
						vis[A] = vis[B] = false;
						
						G[A].pb(B);
						G[B].pb(A);
					}
				}
				
				ans[pos] = dfs(findx(a[pos]));
				
				for(auto edge : v){
					if(neww[edge] >= b[pos]){
						int A = findx(l[edge]);
						int B = findx(r[edge]);
						G[A].pop_back();
						G[B].pop_back();
					}
				}
			}
		}
		fr(i, bi*bsz, min(q, (bi+1)*bsz)){
			if(t[i] == 1){
				w[a[i]] = b[i];
			}
		}
	}
	fr(i, 0, q){
		if(t[i] == 2){
			cout<<ans[i]<<endl;
		}
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();	
}

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