제출 #523947

#제출 시각아이디문제언어결과실행 시간메모리
523947Koosha_mv다리 (APIO19_bridges)C++14
59 / 100
3082 ms13632 KiB
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define per(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
 
const int N=2e5+99,S=422;
 
int n,m,q,act[N],actsz,a[N],b[N],s[N],t[N],w[N],pw[N],cw[N],par[N],rap[N],ans[N],mark[N],type[N],pert[N],sz,mv[N];
vector<int> v[N];
 
bool cmp(int i,int j){
	return b[i]>b[j];
}
void reset(){
	rep(i,0,actsz){
		par[act[i]]=rap[act[i]];
	}
	actsz=0;
}
inline int getpar(int u,int s){
	if(s==1 && 0){
		while(par[u]>0){
			u=par[u];
		}
		return u;
	}
	else{
		if(par[u]<0) return u;
		int i=0;
		mv[i]=u;
		while(1){
			if(par[mv[i]]<0) break;
			mv[i+1]=par[mv[i]];
			i++;
		}
		rep(j,0,i){
			par[mv[j]]=mv[i];
		}
		if(s==0){
			rep(j,0,i){
				rap[mv[j]]=mv[i];
			}
		}
		else{
			rep(j,0,i-1){
				act[actsz++]=mv[j];
			}
		}
		return mv[i];
	}
}
inline void merge(int u,int v,int s){
	u=getpar(u,s),v=getpar(v,s);
	if(u==v) return ;
	if(par[u]>par[v]) swap(u,v);
	if(s==0){
		par[u]+=par[v];
		rap[u]+=rap[v];
		
		par[v]=u;
		rap[v]=u;
	}
	else{
		act[actsz++]=u;
		act[actsz++]=v;
		par[u]+=par[v];
		par[v]=u;
	}
}
void solve(int l,int r){
	fill(mark,mark+m,0);
	fill(par,par+n+10,-1);
	fill(rap,rap+n+10,-1);
	vector<int> vec;
	rep(i,0,m){
		w[i]=cw[i];
	}
	rep(i,0,l){
		if(type[i]==1){
			w[a[i]]=b[i];		
		}
	}
	rep(i,0,m){
		pw[i]=w[i];
	}
	rep(i,l,r){
		if(type[i]==1){
			mark[a[i]]=1;
		}
		else{
			vec.pb(i);
		}
	}
	int p=N-1;
	rep(i,0,m){
		if(!mark[i]){
			//eror(i);
			v[w[i]].pb(i);			
		}
	}
	sort(all(vec),cmp);
	for(auto id : vec){
		//eror(id);
		rep(i,l,id){
			if(type[i]==1){
				pw[a[i]]=b[i];
			}
		}
		while(b[id]<=p){
			for(auto x : v[p]){
				mv[sz++]=s[x];
				mv[sz++]=t[x];
				merge(s[x],t[x],0);	
			}
			p--;
		}
		rep(i,0,sz){
			getpar(mv[i],0);
		}
		sz=0;
		rep(i,l,r){
			//cout<<i<<" -> "<<pw[a[i]]<<endl;
			if(b[id]<=pw[a[i]]){
				merge(s[a[i]],t[a[i]],1);
			}
		}
		ans[id]=-par[getpar(a[id],1)];
		rep(i,l,id){
			if(type[i]==1){
				pw[a[i]]=w[a[i]];
			}
		}
		if(actsz>20000){
			assert(0);
		}
		reset();
	}
	rep(i,0,N){
		v[i].clear();
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	srand(time(NULL));
	vector<int> vec;
	cin>>n>>m;
	rep(i,0,m){
		cin>>s[i]>>t[i]>>w[i];
		vec.pb(w[i]);
	}
	cin>>q;
	rep(i,0,q){
		cin>>type[i]>>a[i]>>b[i];
		if(type[i]==1) a[i]--;
		vec.pb(b[i]);
	}
	sort(all(vec));
	rep(i,0,m){
		w[i]=lower_bound(all(vec),w[i])-vec.begin();
		cw[i]=w[i];
	}
	rep(i,0,q){
		b[i]=lower_bound(all(vec),b[i])-vec.begin();
	}
	for(int i=0;i<q;i+=S){
		solve(i,min(q,i+S));
	}
	rep(i,0,q){
		if(type[i]==1) continue ;
		cout<<ans[i]<<" ";
	}
}
/*
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
6
1 1 1
1 2 3
1 5 2
1 3 1
1 8 1
2 1 1
*/
#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...