Submission #834197

#	Time	Username	Problem	Language	Result	Execution time	Memory
834197		Antekb	Bridges (APIO19_bridges)	C++17	100 / 100	1909 ms	10224 KiB

bridges

#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t)){
		cerr<<", ";
	}
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1e5+5;
vii edg;
vii E[N];
int wei[N];
int ans[N];
int spec[N], wei2[N];
int r[N], siz[N], vis[N];
int find(int v){
	if(r[v]==v)return v;
	return r[v]=find(r[v]);
}
void Union(int a, int b){
	a=find(a);
	b=find(b);
	if(a==b)return;
	if(siz[a]<siz[b])swap(a, b);
	r[b]=a;
	siz[a]+=siz[b];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin>>n>>m;
	for(int i=0; i<m; i++){
		int u, v, w;
		cin>>u>>v>>w;
		wei[i]=w;
		edg.eb(u, v);
	}
	int q;
	cin>>q;
	int K=800;
	vector<pair<pii, int> > Q, U;
	for(int qq=0; qq<q; qq++){
		int qt, qa, qb;
		cin>>qt>>qa>>qb;
		if(qt==1)U.eb(mp(qb, qa-1), qq);
		else Q.eb(mp(qb, qa), qq);
		if(qq==q-1 || Q.size()+U.size()==K){
			vi waz, waz2;
			for(auto i:U){
				waz.pb(i.st.nd);
				waz2.pb(edg[i.st.nd].st);
				waz2.pb(edg[i.st.nd].nd);
				spec[i.st.nd]=1;
				wei2[i.st.nd]=wei[i.st.nd];
			}
			sort(all(waz));
			waz.resize(unique(all(waz))-waz.begin());
			sort(all(waz2));
			waz2.resize(unique(all(waz2))-waz2.begin());
			vector<pair<int, pii> > edg2;
			for(int i=0; i<m ;i++){
				if(!spec[i])edg2.eb(wei[i], edg[i]);
			}
			for(int i=1; i<=n; i++)r[i]=i, siz[i]=1;
			sort(all(edg2));
			reverse(all(edg2));
			sort(all(Q));
			reverse(all(Q));
			int wsk=0;
			for(int j=0; j<Q.size(); j++){
				while(wsk<edg2.size() && edg2[wsk].st>=Q[j].st.st){
					Union(edg2[wsk].nd.st, edg2[wsk].nd.nd);
					wsk++;
				}
				int t=Q[j].nd;
				for(auto i:U){
					if(i.nd>t)break;
					wei2[i.st.nd]=i.st.st;
				}
				for(int i:waz){
					E[find(edg[i].st)].eb(find(edg[i].nd), i);
					E[find(edg[i].nd)].eb(find(edg[i].st), i);
				}
				//deb(Q[j].st.nd, Q[j].st.nd, Q[j].nd);
				//for(int i=0; i<m; i++){deb(find(edg[i].st), find(edg[i].nd), spec[i], wei[i], wei2[i]);}
				vi V;
				int s=0;
				V.pb(find(Q[j].st.nd));
				vis[V[0]]=1;
				for(int i=0; i<V.size(); i++){
					int v=V[i];
					//deb(v, siz[v]);
					s+=siz[v];
					for(auto e:E[v]){
						int u=e.st;
						//deb(v, u, e.nd);
						if(wei2[e.nd]>=Q[j].st.st && !vis[u]){
							vis[u]=1;
							V.pb(u);
						}
					}
				}
				ans[Q[j].nd]=s;
				for(int i:V){
					vis[i]=0;
				}
				for(auto i:waz){wei2[i]=wei[i];}
				for(auto i:waz2){
					E[find(i)].clear();
				}
			}
			for(auto i:U){
				spec[i.st.nd]=0;
				wei[i.st.nd]=i.st.st;
				wei2[i.st.nd]=0;
			}
			Q.clear();
			U.clear();
		}
	}
	for(int i=0; i<q; i++){
		if(ans[i]){
			cout<<ans[i]<<"\n";
		}
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:65:34: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |   if(qq==q-1 || Q.size()+U.size()==K){
      |                 ~~~~~~~~~~~~~~~~~^~~
bridges.cpp:88:18: 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]
   88 |    for(int j=0; j<Q.size(); j++){
      |                 ~^~~~~~~~~
bridges.cpp:89:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     while(wsk<edg2.size() && edg2[wsk].st>=Q[j].st.st){
      |           ~~~^~~~~~~~~~~~
bridges.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i=0; i<V.size(); i++){
      |                  ~^~~~~~~~~

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