Submission #409779

#	Time	Username	Problem	Language	Result	Execution time	Memory
409779		amunduzbaev	Bridges (APIO19_bridges)	C++14	100 / 100	2495 ms	112660 KiB

bridges

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int BLOK=1000;
pair<PII,int>edge[MAXN];
pair<int,PII>query[MAXN];
int ans[MAXN],ata[MAXN],sz[MAXN];
bool ban[MAXN],ban1[MAXN];
stack<int>st;
vector<pair<PII,int> >history;
int tap(int x){
	if(ata[x]==x)return x;
	return tap(ata[x]);	
}
bool merge(PII v){
	int x=tap(v.ff),y=tap(v.ss);
	if(x==y)return 0;
	if(sz[x]<sz[y])swap(x,y);
	history.pb(mp(mp(x,y),sz[y]));
	ata[y]=x;sz[x]+=sz[y]; return 1;	
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("file.in", "r", stdin);
    int n,m;
    cin>>n>>m;
    set<PII>edges;
    for(int i=1;i<=m;i++){
    	int u,v,w;
		cin>>u>>v>>w;
		edge[i]=mp(mp(u,v),w);
		edges.insert(mp(w,i));
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
    	int t,a,b;
		cin>>t>>a>>b;
		query[i]=mp(t,mp(a,b));	
    }
    for(int i=1;i<=q;i+=BLOK){
    	memset(ban,0,sizeof ban);
    	for(int i=1;i<=n;i++)ata[i]=i,sz[i]=1;
    	vector<PII>v,g;int r=min(i+BLOK-1,q);
    	for(int j=i;j<=r;j++){
    		if(query[j].ff==1)
    			ban[query[j].ss.ff]=j;
    		else
    			g.pb(mp(query[j].ss.ss,j));
    	}
    	tr(it,edges)
    		if(!ban[it->ss])
    			v.pb(*it);
    	sort(all(g));
		int p=int(v.size())-1,rec;
    	for(int j=int(g.size())-1,ind,k;j>=0;j--){
    		rec=0;
    		while(p>=0 and v[p].ff>=g[j].ff)
				merge(edge[v[p].ss].ff),p--;
			for(k=g[j].ss-1;k>=i;k--){
				ind=query[k].ss.ff;
				if(query[k].ff==1 and !ban1[ind]){
					if(query[k].ss.ss>=g[j].ff)rec+=merge(edge[ind].ff);
					ban1[ind]=1;st.push(ind);
				}
			}
			for(k=g[j].ss+1;k<=r;k++){
				ind=query[k].ss.ff;
				if(query[k].ff==1 and !ban1[ind]){
					if(edge[ind].ss>=g[j].ff)rec+=merge(edge[ind].ff);
					ban1[ind]=1;st.push(ind);	
				}
			}
			ans[g[j].ss]=sz[tap(query[g[j].ss].ss.ff)];
			while(!st.empty())ban1[st.top()]=0,st.pop();
			while(rec--){ //x,y,sz[y]
				int y=history.back().ff.ss;
				sz[history.back().ff.ff]-=history.back().ss;ata[y]=y;
				history.ppb();	
			}
    	}
    	for(int j=i,a;j<=r;j++)
    		if(query[j].ff==1){
    			a=query[j].ss.ff;
    			edges.erase(mp(edge[a].ss,a));
				edge[a].ss=query[j].ss.ss;	
    			edges.insert(mp(edge[a].ss,a));
			}
    }
    for(int i=1;i<=q;i++){
    	if(query[i].ff==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