Submission #146528

#	Time	Username	Problem	Language	Result	Execution time	Memory
146528		username	Bridges (APIO19_bridges)	C++14	46 / 100	3018 ms	9068 KiB

bridges

#pragma GCC optimize("O3")
#include<stdint.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#define mid (l+r>>1)
#define lch (idx*2+1)
#define rch (idx*2+2)
/*****************************************************************************/
#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 __debug
#ifdef __debug
	#define IOS (void)0
	#define de(...) cerr<<__VA_ARGS__
	#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
#else
	#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define de(...) (void)0
	#define ar(...) (void)0
#endif
/***********************************default***********************************/
struct tup{int F,S,T;};
const int maxn=5e4+9,maxm=1e5+9,maxq=1e5+9,bl=250;
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;
bool mrk[maxm];
 
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;
	int z=0;
	REP(i,0,q)cin>>qrs[i].F>>qrs[i].S>>qrs[i].T,--qrs[i].S,qrs[i].T=-qrs[i].T,z+=qrs[i].F==2;
//	assert(z*n<2e8);
	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()){
			REP(j,0,n)mrk[i]=0;
			REP(j,l,r)if(qrs[j].F==1)mrk[qrs[j].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){
				st.erase(st.find({eds[qq.S].T,qq.S}));
				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:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
bridges.cpp: In function 'int main()':
bridges.cpp:21:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
bridges.cpp:84:3: note: in expansion of macro 'REP'
   REP(i,0,p.size()){
   ^~~

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