Submission #523910

#	Time	Username	Problem	Language	Result	Execution time	Memory
523910		Koosha_mv	Bridges (APIO19_bridges)	C++14	59 / 100	3061 ms	13144 KiB

bridges

#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=400;

int n,m,q,a[N],b[N],s[N],t[N],w[N],pw[N],cw[N],par[N],rap[N],ans[N],mark[N],type[N];
vector<int> act,v[N];

bool cmp(int i,int j){
	return b[i]>b[j];
}
void reset(){
	for(auto x : act){
		par[x]=rap[x];
	}
	act.clear();
}
int getpar(int u,int s){
	if(par[u]<0) return u;
	int p=getpar(par[u],s);
	if(s==1) return p;
	if(s==0){
		par[u]=p;
		rap[u]=p;
	}
	else{
		act.pb(u);
		par[u]=p;
	}
	return par[u];
}
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.pb(u);
		act.pb(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]){
				//eror(x);
				merge(s[x],t[x],0);	
			}
			p--;
		}
		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(act.size()>2000){
			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
*/

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