Submission #535027

#TimeUsernameProblemLanguageResultExecution timeMemory
535027new_accBridges (APIO19_bridges)C++14
13 / 100
3088 ms5432 KiB
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
struct st{
	int a,b,c;
};
int fau[N],siz[N],c[N],res[N];
pair<int,int>w[N];
bitset<N>pom;
bitset<N>pom2;
vi roolf;
st zap[N];
int Find(int a){
	while(fau[a]!=a) a=fau[a];
	return a;
}
void Union(int a,int b){
	a=Find(a),b=Find(b);
	if(a==b) return;
	if(siz[a]>siz[b]) swap(a,b);
	fau[a]=b,siz[b]+=siz[a];
	roolf.push_back(a);
}
void rollback(int x){
	if(x==0) return;
	int u=roolf.back();
	roolf.pop_back();
	siz[fau[u]]-=siz[u];
	fau[u]=u;
	rollback(x-1);
}	
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) fau[i]=i,siz[i]=1;
	for(int i=1;i<=m;i++) cin>>w[i].fi>>w[i].se>>c[i];
	int q;
	cin>>q;
	for(int i=1;i<=q;i++) cin>>zap[i].a>>zap[i].b>>zap[i].c;
	int p=sqrt(q)*10;
	for(int i=1;i<=q;i+=p){
		vector<pair<int,int> >sorted;
		vector<pair<int,int> >aktz;
		for(int j=i;j<=min(q,i+p-1);j++){
			if(zap[j].a==1) pom[zap[j].b]=1;
			else aktz.push_back({zap[j].c,j});
		}
		for(int j=1;j<=m;j++){
			if(pom[j]) continue;
			sorted.push_back({c[j],j});
		}
		sort(sorted.begin(),sorted.end());
		sort(aktz.begin(),aktz.end());
		reverse(aktz.begin(),aktz.end());
		int wsk=sorted.size()-1;
		for(auto u:aktz){
			while(wsk>=0 and sorted[wsk].fi>=u.fi) Union(w[sorted[wsk].se].fi,w[sorted[wsk].se].se),wsk--;
			int ile=0;
			for(int j=u.se-1;j>=i;j--){
				if(zap[j].a==2 or pom2[zap[j].b]) continue;
				pom2[zap[j].b]=1;
				if(zap[j].c>=u.fi and Find(w[zap[j].b].fi)!=Find(w[zap[j].b].se)) ile++,Union(w[zap[j].b].fi,w[zap[j].b].se);
			}	
			for(int j=u.se+1;j<=min(q,i+p-1);j++){
				if(zap[j].a==2 or pom2[zap[j].b]) continue;
				if(c[zap[j].b]>=u.fi and Find(w[zap[j].b].fi)!=Find(w[zap[j].b].se)) ile++,Union(w[zap[j].b].fi,w[zap[j].b].se);
			}
			res[u.se]=siz[Find(zap[u.se].b)];
			rollback(ile);
			for(int j=u.se-1;j>=1;j--) pom2[zap[j].b]=0;
		}
		for(int j=1;j<=n;j++) fau[j]=j,siz[j]=1;
		roolf.clear();
		for(int j=i;j<=min(q,i+p-1);j++){
			if(zap[j].a==1) c[zap[j].b]=zap[j].c;
			pom[zap[j].b]=0;
		}
	}
	for(int i=1;i<=q;i++) if(zap[i].a==2) cout<<res[i]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...