Submission #934158

#	Time	Username	Problem	Language	Result	Execution time	Memory
934158		amirhoseinfar1385	Bridges (APIO19_bridges)	C++17	100 / 100	1655 ms	10176 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10,maxm=100000+10,sq=1500;
int n,m,q,res[maxm];
struct yal{
	int u,v,w,tagh,asl;
}alle[maxm];
struct qu{
	int qq,ind,w;
}allq[maxm];
struct dsu{
	vector<int>allv;
	int par[maxn],sz[maxn];
	dsu(){
		for(int i=1;i<maxn;i++){
			par[i]=i;
			sz[i]=1;
		}
	}
	void clear(){
		allv.clear();
		for(int i=1;i<maxn;i++){
			par[i]=i;
			sz[i]=1;
		}
	}
	int root(int u){
		if(u==par[u]){
			return u;
		}
		return root(par[u]);
	}
	void con(int u,int v){
		int rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			if(sz[rootu]<sz[rootv]){
				swap(rootu,rootv);
			}
			allv.push_back(rootv);
			par[rootv]=rootu;
			sz[rootu]+=sz[rootv];
			return ;
		}
		allv.push_back(-1);
	}
	int gets(int u){
		return sz[root(u)];
	}
	void back(){
		int x=allv.back();
		allv.pop_back();
		if(x==-1){
			return ;
		}
		sz[par[x]]-=sz[x];
		par[x]=x;
	}
}ds;
vector<int>allp,allind,allval,que[maxm];
bool cmp(int a,int b){
	if(alle[a].w!=alle[b].w){
		return alle[a].w<alle[b].w;
	}
	if(alle[a].u!=alle[b].w){
		return alle[a].u<alle[b].u;
	}
	return alle[a].v<alle[b].v;
}

void vorod(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>alle[i].u>>alle[i].v>>alle[i].w;
		alle[i].w*=-1;
		alle[i].tagh=0;
		alle[i].asl=alle[i].w;
		allind.push_back(i);
	}
	sort(allind.begin(),allind.end(),cmp);
	for(auto x:allind){
		allval.push_back(alle[x].w);
	}	
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>allq[i].qq>>allq[i].ind>>allq[i].w;
		allq[i].w*=-1;
	}
}

void calq(int ind){
	for(auto x:que[ind]){
		int l=x-(x%sq);
		for(int i=l;i<x;i++){
			if(allq[i].qq==1){
				alle[allq[i].ind].w=allq[i].w;
			}
		}
		for(auto y:allp){
			if(allq[x].w>=alle[y].w){
				ds.con(alle[y].u,alle[y].v);
			}
		}
		res[x]=ds.gets(allq[x].ind);
		for(auto y:allp){
			if(allq[x].w>=alle[y].w){
				ds.back();
			}
		}
		for(int i=l;i<x;i++){
			if(allq[i].qq==1){
				alle[allq[i].ind].w=alle[allq[i].ind].asl;
			}
		}
	}
	que[ind].clear();
}

void solve(){
	for(int l=0;l<q;l+=sq){
		sort(allind.begin(),allind.end(),cmp);
		allval.clear();
		for(auto x:allind){
			allval.push_back(alle[x].w);
		}	
		ds.clear();
		allp.clear();
		for(int i=l;i<min(q,l+sq);i++){
			if(allq[i].qq==1){
				alle[allq[i].ind].tagh=1;
				allp.push_back(allq[i].ind);
			}
			else{
				int p=upper_bound(allval.begin(),allval.end(),allq[i].w)-allval.begin();
				que[p].push_back(i);
			}
		}
		for(int i=0;i<(int)allind.size();i++){
			calq(i);
			if(alle[allind[i]].tagh==0){
				ds.con(alle[allind[i]].u,alle[allind[i]].v);
			}
		}
		calq((int)allind.size());
		for(int i=l;i<min(q,l+sq);i++){
			if(allq[i].qq==1){
				alle[allq[i].ind].tagh=0;
				alle[allq[i].ind].w=alle[allq[i].ind].asl=allq[i].w;
			}
		}
	}
}

void khor(){
	for(int i=0;i<q;i++){
		if(allq[i].qq==2)
			cout<<res[i]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();	
	solve();
	khor();
}

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