Submission #146496

#	Time	Username	Problem	Language	Result	Execution time	Memory
146496		username	Bridges (APIO19_bridges)	C++14	30 / 100	3099 ms	10852 KiB

bridges

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define RREP(i,j,k) for(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=280;
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 r){
	if(x==fa[x])return x;
	else{
		if(r)rf.pb({x,fa[x]});
		return fa[x]=find(fa[x],r);
	}
}

void unite(int x,int y,bool r){
	x=find(x,r),y=find(y,r);
	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,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,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,1);
					mrk[tq.s]=0;
				}
			}
			res[p[i]]=sz[find(qq.s,1)];
			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:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
bridges.cpp: In function 'int main()':
bridges.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
bridges.cpp:63: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