제출 #166469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
166469		Feeder	다리 (APIO19_bridges)	C++11	0 / 100	3032 ms	13944 KiB

bridges

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

int par[50001], sz[50001], rnk[50001];

int findp(int x){
	return x == par[x] ? x : findp(par[x]);
}

void merge(int x, int y){
	x = findp(x), y = findp(y);
	if(x == y) return;
	if(rnk[x] < rnk[y]) swap(x, y);
	par[y] = x;
	if(rnk[x] == rnk[y]) rnk[x]++;
	sz[x] += sz[y];
}

void split(int x, int y, int w){
	if(w) rnk[x]--;
	par[y] = y;
	sz[x] -= sz[y];
}

int n, m, a, b, w, q, t, rt, edgea[100001], edgeb[100001], warr[50001], ans[100001];
multiset<tuple<int, int> > edgelist;
vector<tuple<int, int, int> > uvec; // query, bridge, weight
vector<tuple<int, int, int> > qvec; // weight, query, island
set<int> cbridges;
int qcnt = 0;

void findans(int qnum){
	//cout << "findans: " << qnum << endl;
	stack<tuple<int, int, int> > st;
	set<int> added;
	int qw, qi, qq;
	tie(qw, qq, qi) = qvec[qnum];
	for(int i=int(uvec.size())-1; i>=0; i--){
		if(get<0>(uvec[i]) > qq) continue;
		int bnum = get<1>(uvec[i]);
		w = get<2>(uvec[i]);
		if(added.count(bnum)) continue;
		added.insert(bnum);
		if(w < qw) continue;
		a = edgea[bnum], b = edgeb[bnum];
		a = findp(a), b = findp(b);
		//cout << a << ' ' << b << ' ' << w << endl;
		if(a == b) continue;
		if(rnk[a] < rnk[b]) swap(a, b);
		if(rnk[a] == rnk[b]) st.emplace(a, b, 1);
		else st.emplace(a, b, 0);
		merge(a, b);
	}
	ans[qq] = sz[findp(qi)];
	while(!st.empty()){
		tie(a, b, w) = st.top();
		st.pop();
		split(a, b, w);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		cin >> edgea[i] >> edgeb[i] >> w;
		edgelist.insert(make_tuple(-w, i));
		warr[i] = w;
	}
	
	cin >> q;
	fill(ans, ans + q, -1);
	rt = sqrt(q);
	for(int i=0; i<q; i++){
		cin >> t >> a >> b;
		if(t == 1){
			uvec.emplace_back(i, a, b);
			cbridges.insert(a);
		}
		else qvec.emplace_back(b, i, a);
		if(i % rt != rt - 1 && i != q - 1) continue;
		
		qcnt = int(qvec.size()) - 1;
		sort(qvec.begin(), qvec.end());
		for(auto it:cbridges){
			uvec.emplace_back(-1, it, warr[it]);
		}
		sort(uvec.begin(), uvec.end());
		for(int j=1; j<=n; j++) par[j] = j;
		fill(sz + 1, sz + n + 1, 1);
		fill(rnk + 1, rnk + n + 1, 0);
		for(auto it:edgelist){
			tie(w, a) = it;
			w = -w;
			while(qcnt >= 0 && get<0>(qvec[qcnt]) > w){
				findans(qcnt);
				qcnt--;
			}
			if(cbridges.count(a)) continue;
			b = edgeb[a];
			a = edgea[a];
			//cout << "merge: " << a << ' ' << b << endl;
			merge(a, b);
		}
		while(qcnt >= 0){
			findans(qcnt);
			qcnt--;
		}
		
		for(int j=int(uvec.size())-1; j>=0; j--){
			b = get<1>(uvec[j]), w = get<2>(uvec[j]);
			if(cbridges.count(b) == 0) continue;
			edgelist.erase(edgelist.find(make_tuple(-warr[b], b)));
			edgelist.insert(make_tuple(-w, b));
			warr[b] = w;
			cbridges.erase(b);
		}
		
		uvec.clear();
		qvec.clear();
		cbridges.clear();
	}
	for(int i=0; i<q; i++){
		if(ans[i] != -1) cout << ans[i] << '\n';
	}
}

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