Submission #146476

#	Time	Username	Problem	Language	Result	Execution time	Memory
146476		username	Bridges (APIO19_bridges)	C++14	0 / 100	170 ms	11816 KiB

bridges

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)

struct tup{int F,S,T;};
const int maxn=5e4+9,maxm=1e5+9,maxq=1e5+9,bl=177;
int n,m,q,fa[maxn],sz[maxn],res[maxq];
tup eds[maxm],qrs[maxq];
set<pii>st;
vector<pii>rf,rs;
vector<int>p;
bitset<maxm>mrk;

void init(int k){REP(i,0,k)fa[i]=i,sz[i]=1;}

int find(int x,bool c){return x==fa[x]?x:c?fa[x]=find(fa[x],c):find(fa[x],c);}

void unite(int x,int y,bool c,bool r){
	x=find(x,c),y=find(y,c);
	if(x==y)return;
	if(sz[x]>sz[y])swap(x,y);
	if(r)rf.pb({x,fa[x]}),rs.pb({y,sz[y]});
	fa[x]=y,sz[y]+=sz[x];
}

void restore(){
	RREP(i,rf.size(),0)fa[rf[i].F]=rf[i].S;
	RREP(i,rs.size(),0)sz[rs[i].F]=rs[i].S;
}

main(){
	IOS;
	cin>>n>>m;
	REP(i,0,m){
		int u,v,w;cin>>u>>v>>w,--u,--v,w=-w;
		eds[i]={u,v,w};
		st.insert({w,i});
	}
	cin>>q;
	REP(i,0,q)cin>>qrs[i].F>>qrs[i].S>>qrs[i].T,--qrs[i].S,qrs[i].T=-qrs[i].T;
	for(int l=0;l<q;l+=bl){
		int r=min(l+bl,q);
		p.clear();
		REP(i,l,r)if(qrs[i].F==2)p.pb(i);
		sort(ALL(p),[](int a,int b){return qrs[a].T<qrs[b].T;});
		init(n);
		auto it=st.begin();
//		REP(i,0,p.size()){
//			mrk.reset();
//			REP(i,l,r)if(qrs[i].F==1)mrk[qrs[i].S]=1;
//			tup&qq=qrs[p[i]];
//			while(it!=st.end()&&it->F<=qq.T){
//				if(!mrk[it->S])unite(eds[it->S].F,eds[it->S].S,1,0);
//				++it;
//			}
//			rf.clear(),rs.clear();
//			RREP(j,p[i],l){
//				tup&tq=qrs[j];
//				if(tq.F==1&&mrk[tq.S]){
//					if(tq.T<=qq.T)unite(eds[tq.S].F,eds[tq.S].S,0,1);
//					mrk[tq.S]=0;
//				}
//			}
//			REP(j,p[i],r){
//				tup&tq=qrs[j];
//				if(tq.F==1&&mrk[tq.S]){
//					if(eds[tq.S].T<=qq.T)unite(eds[tq.S].F,eds[tq.S].S,0,1);
//					mrk[tq.S]=0;
//				}
//			}
//			res[p[i]]=sz[find(qq.S,0)];
//			restore();
//		}
		REP(i,l,r){
			tup&qq=qrs[i];
			if(qq.F==1){
				auto it=st.find({eds[qq.S].T,qq.S});
				st.erase(it);
				st.insert({eds[qq.S].T=qq.T,qq.S});
			}
		}
	}
	REP(i,0,q)if(qrs[i].F==2)cout<<res[i]<<endl;
}

Compilation message (stderr)

bridges.cpp:40:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
bridges.cpp: In function 'int main()':
bridges.cpp:56:8: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   auto it=st.begin();
        ^~

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