Submission #367472

#TimeUsernameProblemLanguageResultExecution timeMemory
367472YJUBridges (APIO19_bridges)C++14
13 / 100
3080 ms10336 KiB
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long 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=750;
#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;
	bool operator < (edge _a){
		return (c<_a.c);
	}
}ed[N];

vector<edge> unchanged;
vector<ll> query,changed;
ll n,m,q,ty[N],id[N],w[N],ans[N],vis[N],col=1,tag[N];

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

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

void uni(ll a,ll b){
	//cout<<"uni "<<a<<" "<<b<<"\n";
	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];
	}
}

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();
		memset(vis,0,sizeof(vis));
		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(ed[j]);
		//sort
		sort(unchanged.rbegin(),unchanged.rend());
		sort(query.begin(),query.end(),[&](ll a,ll b){
			return w[a]>w[b];
		});
		//
		//
		//cout<<"query\n";
		ll pos=0;
		for(auto j:query){
			//cout<<ty[j]<<" "<<id[j]<<" "<<w[j]<<"\n";
			while(pos<SZ(unchanged)&&unchanged[pos].c>=w[j])uni(unchanged[pos].x,unchanged[pos].y),++pos;
			ll ti=0;
			for(int ii=j-1;ii>=ql;ii--){
				if(ty[ii]==1&&tag[id[ii]]!=col){
					tag[id[ii]]=col;
					if(w[ii]>=w[j]){
						++ti;
						uni(ed[id[ii]].x,ed[id[ii]].y);
					}
				}
			}
			for(auto ii:changed){
				if(tag[ii]!=col){
					tag[ii]=col;
					if(ed[ii].c>=w[j]){
						++ti;
						uni(ed[ii].x,ed[ii].y);
					}
				}
			}
			ans[j]=sz[f(id[j])];
			while(ti)undo(),ti--;
			++col;
		}
		
		//change
		for(int j=ql;j<=qr;++j){
			if(ty[j]==1){ed[id[j]].c=w[j];}
		}
	}
	REP1(i,q)if(ty[i]==2)cout<<ans[i]<<"\n";
	return 0;
}

#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...