Submission #950052

#	Time	Username	Problem	Language	Result	Execution time	Memory
950052		Saul0906	Bridges (APIO19_bridges)	C++14	100 / 100	2246 ms	7480 KiB

bridges

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define rep2(a,b,c,d) for(int a=b; a<c; a+=d)
#define repa(a, b) for(auto a:b)
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

using namespace std;

struct edge{
	int u, v, w;
	bool operator<(const edge edge2)const{
		return w>edge2.w;
	}
};

struct rback{
	int a, b, c, d;
};

int n, m, q;
const int lim=1e5+5;
edge e[lim], qr[lim];
vector<pii> ewu, qry;
vector<edge> enu;
stack<rback> rbk;
pii dsu[lim];
bool upd[lim];

int find(int u){
	if(dsu[u].fi==u) return u;
	return find(dsu[u].fi);
}

void join(edge a, bool rb){
	int x=find(a.u), y=find(a.v);
	if(x==y) return;
	if(dsu[x].se<dsu[y].se) swap(x,y);
	if(rb) rbk.push({x,dsu[x].se,y,dsu[y].fi});
	dsu[x].se+=dsu[y].se;
	dsu[y].fi=x;
}

void djoin(){
	while(rbk.size()){
		int a=rbk.top().a, b=rbk.top().b, c=rbk.top().c, d=rbk.top().d;
		dsu[a].se=b;
		dsu[c].fi=d;
		rbk.pop();
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	rep(i,1,m+1) cin>>e[i].u>>e[i].v>>e[i].w;
	cin>>q;
	rep(i,0,q) cin>>qr[i].u>>qr[i].v>>qr[i].w;
	vector<pii> ans;
	rep2(i,0,q,500){
		int r=min(i+(int)(500),q), l=0;
		rep(j,1,m+1) upd[j]=false;
		rep(j,i,r){
			if(qr[j].u==1) upd[qr[j].v]=true;
			else qry.pb({qr[j].w,j});
		}
		rep(j,1,m+1){
			if(!upd[j]) enu.pb(e[j]);
			else ewu.pb({j,e[j].w});
		}
		rep(j,1,n+1) dsu[j]={j,1};
		sort(qry.begin(),qry.end());
		reverse(qry.begin(),qry.end());
		sort(enu.begin(),enu.end());
		repa(j,enu){
			while(l<qry.size() && qry[l].fi>j.w){
				repa(k,ewu) e[k.fi].w=k.se;
				rep(k,i,qry[l].se) if(qr[k].u==1) e[qr[k].v].w=qr[k].w;
				repa(k,ewu) if(e[k.fi].w>=qry[l].fi) join(e[k.fi],true);
				ans.pb({qry[l].se,dsu[find(qr[qry[l].se].v)].se});
				//cout<<ans.back().fi<<" "<<ans.back().se<<endl;
				djoin();
				l++;
			}
			//cout<<j.u<<" "<<j.v<<" "<<j.w<<" "<<qry[l].fi<<endl;
			join(j,false);
		}
		while(l<qry.size()){
			repa(k,ewu) e[k.fi].w=k.se;
			rep(k,i,qry[l].se) if(qr[k].u==1) e[qr[k].v].w=qr[k].w;
			repa(k,ewu) if(e[k.fi].w>=qry[l].fi) join(e[k.fi],true);
			ans.pb({qry[l].se,dsu[find(qr[qry[l].se].v)].se});
			djoin();
			l++;
			//cout<<ans.back().fi<<" "<<ans.back().se<<endl;
		}
		rep(k,i,r) if(qr[k].u==1) e[qr[k].v].w=qr[k].w;
		ewu.clear();
		enu.clear();
		qry.clear();
	}
	sort(ans.begin(),ans.end());
	repa(aa,ans) cout<<aa.se<<endl;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:80:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    while(l<qry.size() && qry[l].fi>j.w){
      |          ~^~~~~~~~~~~
bridges.cpp:92:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   while(l<qry.size()){
      |         ~^~~~~~~~~~~

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