Submission #367491

#	Time	Username	Problem	Language	Result	Execution time	Memory
367491		YJU	Bridges (APIO19_bridges)	C++14	100 / 100	2967 ms	130676 KiB

bridges

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e5+5;
const ld pi=acos(-1);
//const ll INF=(1LL<<60);
const ll B=1000;
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

struct edge{
	ll x,y,c;
}ed[N];

vector<ll> query,changed,join[N],unchanged;
ll n,m,q,ty[N],id[N],w[N],ans[N];

bitset<N>vis;

ll dir[N],sz[N],stk[N],now;

inline ll f(ll idx){
	while(idx!=dir[idx])idx=dir[idx];
	return idx;
}

inline void uni(ll a,ll b){
	a=f(a);b=f(b);
	if(sz[a]>sz[b])swap(a,b);
	if(a==b){
		stk[++now]=0;
	}else{
		stk[++now]=a;
		dir[a]=b;
		sz[b]+=sz[a];
	}
}

inline void undo(){
	if(stk[now]==0){
		--now;
	}else{
		ll a=stk[now];
		sz[dir[a]]-=sz[a];
		dir[a]=a;
		--now;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,m)cin>>ed[i].x>>ed[i].y>>ed[i].c;
	cin>>q;
	REP1(i,q)cin>>ty[i]>>id[i]>>w[i];
	for(int i=1;i<=q;i+=B){
		//reset
		unchanged.clear();
		changed.clear();
		query.clear();
		REP1(j,n)dir[j]=j,sz[j]=1;
		//
		ll ql=i,qr=min(i+B,q+1)-1;
		for(int j=ql;j<=qr;++j){
			if(ty[j]==1){
				vis[id[j]]=1;
				changed.pb(id[j]);
			}else{
				query.pb(j);
			}
		}
		REP1(j,m)if(!vis[j])unchanged.pb(j);
		
		for(int j=ql;j<=qr;j++){
			if(ty[j]==1){
				ed[id[j]].c=w[j];
			}else{
				for(auto ii:changed){
					if(ed[ii].c>=w[j])join[j].pb(ii);
				}
			}
		}
		sort(unchanged.begin(),unchanged.end(),[&](ll a,ll b){
			return (ed[a].c>ed[b].c);
		});
		sort(query.begin(),query.end(),[&](ll a,ll b){
			return w[a]>w[b];
		});
		ll pos=0;
		for(auto j:query){
			while(pos<SZ(unchanged)&&ed[unchanged[pos]].c>=w[j])uni(ed[unchanged[pos]].x,ed[unchanged[pos]].y),++pos;
			ll ti=0;
			for(auto ii:join[j])++ti,uni(ed[ii].x,ed[ii].y);
			ans[j]=sz[f(id[j])];
			while(ti)undo(),ti--;
		}
		while(now>0)undo(),--now;
		
		for(int j:changed)vis[j]=0;
	}
	REP1(i,q)if(ty[i]==2)cout<<ans[i]<<"\n";
	return 0;
}

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