Submission #146474

#	Time	Username	Problem	Language	Result	Execution time	Memory
146474		username	Bridges (APIO19_bridges)	C++14	30 / 100	3040 ms	12032 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:5: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:57:3: note: in expansion of macro 'REP'
   REP(i,0,p.size()){
   ^~~

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