Submission #1255963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255963		namhh	Bridges (APIO19_bridges)	C++20	46 / 100	3095 ms	5120 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
const int block = 500;
int n,m,q,u[N],v[N],d[N],par[N],sz[N],check[N],ans[N];
stack<int>st;
vector<int>aqua[block];
vector<int>aqua1;
struct query{
	int type,u,v;
};
query qr[N];
bool cmp1(int a, int b){
	return d[a] > d[b];
}
bool cmp2(int a, int b){
	return qr[a].v > qr[b].v;
}
void init(){
	for(int i = 1; i <= n; i++){
		par[i] = i;
		sz[i] = 1;
	}
}
int find(int u){
	if(u == par[u]) return u;
	return find(par[u]);
}
void join(int u, int v){
	u = find(u);
	v = find(v);
	if(u == v) return;
	st.push(v);
	par[v] = u;
	sz[u] += sz[v];
}
void rollback(int time){
	while(st.size() > time){
		int v = st.top();
		st.pop();
		int u = find(v);
		sz[u] -= sz[v];
		par[v] = v;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> d[i];
	cin >> q;
	for(int i = 1; i <= q; i++) cin >> qr[i].type >> qr[i].u >> qr[i].v;
	for(int i = 1; i <= q; i += block){
		int l = i;
		int r = min(q,i+block-1);
		init();
		vector<int>cc1,cc2;
		for(int j = l; j <= r; j++){
			if(qr[j].type == 1){
				check[qr[j].u] = 1;
				cc1.push_back(j);
			}
			else cc2.push_back(j);
		}
		sort(cc2.begin(),cc2.end(),cmp2);
		for(int j = 1; j <= m; j++) if(!check[j]) aqua1.push_back(j);
		sort(aqua1.begin(),aqua1.end(),cmp1);
		for(int j = l; j <= r; j++){
			if(qr[j].type == 1) d[qr[j].u] = qr[j].v;
			if(qr[j].type == 2){
				for(auto it: cc1){
					if(d[qr[it].u] >= qr[j].v) aqua[j-l].push_back(qr[it].u);
				}
			}
		}
		int cur = 0;
		for(auto it: cc2){
			while(cur < aqua1.size() && d[aqua1[cur]] >= qr[it].v){
				join(u[aqua1[cur]],v[aqua1[cur]]);
				cur++;
			}
			int dz = st.size();
			for(auto it1: aqua[it-l]) join(u[it1],v[it1]);
			ans[it] = sz[find(qr[it].u)];
			rollback(dz);
		}
		aqua1.clear();
		memset(check,0,sizeof(check));
		for(int j = 0; j < block; j++) aqua[j].clear();
		while(!st.empty()) st.pop();
	}
	for(int i = 1; i <= q; i++){
		if(qr[i].type == 2) cout << ans[i] << "\n";
	}
}

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