Submission #524068

#	Time	Username	Problem	Language	Result	Execution time	Memory
524068		Koosha_mv	Bridges (APIO19_bridges)	C++14	100 / 100	2713 ms	10056 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=1e5+99,S=433;
 
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];
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){
	while(par[u]>0){
		u=par[u];
	}
	return u;
}
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]){
			v[w[i]].pb(i);			
		}
	}
	sort(all(vec),cmp);
	for(auto id : vec){
		rep(i,l,id){
			if(type[i]==1){
				pw[a[i]]=b[i];
			}
		}
		while(b[id]<=p){
			for(auto x : v[p]){
				merge(s[x],t[x],0);	
			}
			p--;
		}
		rep(i,l,r){
			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]];
			}
		}
		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; vec.pb(-1);
	cin>>n>>m;
	rep(i,0,m){
		cin>>s[i]>>t[i]>>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]=upper_bound(all(vec),w[i])-vec.begin()-1;
		cw[i]=w[i];
	}
	rep(i,0,q){
		b[i]=upper_bound(all(vec),b[i])-vec.begin()-1;
	}
	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]<<" ";
	}
}

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