Submission #386361

#	Time	Username	Problem	Language	Result	Execution time	Memory
386361		Bill_00	Bridges (APIO19_bridges)	C++14	100 / 100	2702 ms	11360 KiB

bridges

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define N 100005
const int c=1000;
using namespace std;
int n,m,q;
int u[N],v[N],w[N],type[N],a[N],b[N],y[N];
int id[N],sz[N],p[N],ans[N];
int find(int node){
	return (node==p[node]?node:find(p[node]));
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> u[i] >> v[i] >> w[i];
	}
	cin >> q;
	for(int i=1;i<=q;i++){
		cin >> type[i] >> a[i] >> b[i];
	}
	for(int i=0;i<=(q-1)/c;i++){
		for(int j=1;j<=n;j++){
			p[j]=j;
			sz[j]=1;
		}
		vector<pair<pair<int,int>,int> >vv;
		for(int j=i*c+1;j<=min(q,(i+1)*c);j++){
			if(type[j]==1){
				id[a[j]]=i+1;
			}
			else{
				vv.pb({{-b[j],1},j});
			}
		}
		vector<int>vec;
		for(int j=1;j<=m;j++){
			if(id[j]!=(i+1)){
				vv.pb({{-w[j],0},j});
			}
			else{
				vec.pb(j);
			}
		}
		sort(vv.begin(),vv.end());
		for(int j=0;j<vv.size();j++){
			if(vv[j].ff.ss==0){
				int k=vv[j].ss;
				int aa=find(u[k]);
				int bb=find(v[k]);
				if(aa==bb) continue;
				if(sz[aa]>sz[bb]){
					p[bb]=aa;
					sz[aa]+=sz[bb];
				}
				else{
					p[aa]=bb;
					sz[bb]+=sz[aa];
				}
			}
			else{
				stack<pair<pair<int,int>,pair<int,int> > >st;
				int k=vv[j].ss;
				for(int t:vec) y[t]=-1;
				for(int t=i*c+1;t<=k;t++){
					if(type[t]==1){
						y[a[t]]=b[t];
					}
				}
				for(int t=k;t<=min(q,(i+1)*c);t++){
					if(type[t]==1 && y[a[t]]==-1) y[a[t]]=w[a[t]];
				}
				for(int t:vec){
					if(y[t]>=b[k]){
						int aa=find(u[t]);
						int bb=find(v[t]);
						if(aa==bb) continue;
						st.push({{aa,sz[aa]},{bb,sz[bb]}});
						if(sz[aa]>sz[bb]){
							p[bb]=aa;
							sz[aa]+=sz[bb];
						}
						else{
							p[aa]=bb;
							sz[bb]+=sz[aa];
						}
					}
				}
				int aa=find(a[k]);
				ans[k]=sz[aa];
				while(!st.empty()){
					p[st.top().ff.ff]=st.top().ff.ff;
					p[st.top().ss.ff]=st.top().ss.ff;
					sz[st.top().ff.ff]=st.top().ff.ss;
					sz[st.top().ss.ff]=st.top().ss.ss;
					st.pop();
				}
			}
		}
		for(int j=i*c+1;j<=min(q,(i+1)*c);j++){
			if(type[j]==1){
				w[a[j]]=b[j];
			}
		}
	}
	for(int i=1;i<=q;i++){
		if(type[i]==2){
			cout << ans[i] << '\n';
		}
	}

}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int j=0;j<vv.size();j++){
      |               ~^~~~~~~~~~

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