Submission #276504

#	Time	Username	Problem	Language	Result	Execution time	Memory
276504		nafis_shifat	Bridges (APIO19_bridges)	C++14	100 / 100	2496 ms	14132 KiB

bridges

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
int n,m;
int L[mxn];
int R[mxn];
int W[mxn];
 
int vis[mxn]={};
 
vector<int> v;
 
int parent[mxn];
int sz[mxn];
vector<int> adj[mxn];
int block=400;
int findrep(int u) {
	return parent[u]==u ? u : (parent[u]=findrep(parent[u]));
}
void unite(int u,int v) {
	u=findrep(u);
	v=findrep(v);
	if(sz[u]>sz[v]) swap(u,v);
	if(u!=v) {
		parent[u]=v;
		sz[v]+=sz[u];
		
	}
}
struct query {
	int u,w,id,t,id2;
	query(int _,int __,int ___,int ____,int qind) : u(_), w(__), id(___),t(____),id2(qind) {};
};
 
 
int dfs(int cur,int k) {
	vis[cur]=k;
	int ans=sz[cur];
	
	for(int u:adj[cur]) {
		if(vis[u]!=k) {
			ans+=dfs(u,k);
		}
	}
	return ans;
 
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		int U,V,d;
		scanf("%d%d%d",&U,&V,&d);
		L[i]=U;
		R[i]=V;
		W[i]=d;
		v.push_back(i);
	}
	
 
	
 
	int q;
	scanf("%d",&q);
	vector<query> Q;
	int K=0;
	
 
	for(int i=1;i<=q;i++) {
		int t,u,w;
	
		scanf("%d%d%d",&t,&u,&w);
		K+=t-1;
		Q.push_back(query(u,w,i,t,K));
 
	}
	
	int res[mxn];
	int mq[mxn]={};
	int dontuse[mxn]={};
	
	for(int i=1;i<=m;i++)mq[i]=W[i];
	
	int vin=1;
	 sort(v.begin(),v.end(),[](int a,int b) {
	    	return W[a]>W[b];
	 });
	for(int i=0;i<q;i+=block) {
	    
	   
 
 
		for(int j=1;j<=n;j++) {
			parent[j]=j;
			sz[j]=1;
		}
	
		vector<query> cur1;
		vector<query> cur2;
		
 
		for(int j=i;j<min(q,i+block);j++) {
			if(Q[j].t==1) {
				dontuse[Q[j].u]=1;
				cur2.push_back(Q[j]);
			}
 
			else cur1.push_back(Q[j]);
		}
		sort(cur1.begin(),cur1.end(),[](query a,query b) {
			return a.w > b.w;
		});
 
		int lp=0;
		
 
		for(int j=0;j<cur1.size();j++) {
			while(lp<m && W[v[lp]]>=cur1[j].w) {
				if(dontuse[v[lp]]!=1) {
				    unite(L[v[lp]],R[v[lp]]);
				}
				lp++;
			}
			
			
		
		
			
 
			for(int k=0;k<cur2.size();k++) {
				if(cur2[k].id > cur1[j].id ) break;
				
				mq[cur2[k].u]=cur2[k].w;
			}
			
		
			for(int k=0;k<cur2.size();k++) {
			    
				if(mq[cur2[k].u]>=cur1[j].w) {
					int u=L[cur2[k].u];
					int v=R[cur2[k].u];
					
					u=findrep(u);
					v=findrep(v);
					adj[u].push_back(v);
					adj[v].push_back(u);
 
				}
 
 
			}
			int tm=dfs(findrep(cur1[j].u),vin++);
		
			res[cur1[j].id2]=tm;
			for(int k=0;k<cur2.size();k++) {
				if(mq[cur2[k].u]>=cur1[j].w) {
					int u=L[cur2[k].u];
					int v=R[cur2[k].u];
					u=findrep(u);
					v=findrep(v);
					adj[u].clear();
					adj[v].clear();
					
				}
				mq[cur2[k].u]=W[cur2[k].u];
 
			}
 
 
		}
 
 
		for(int j=0;j<cur2.size();j++) {
			W[cur2[j].u]=mq[cur2[j].u]=cur2[j].w;
		}
		
		vector<int> tmp;
		vector<int> ups;
		for(int j=0;j<m;j++) {
			if(dontuse[v[j]]!=1) tmp.push_back(v[j]);
			else ups.push_back(v[j]);
		}

		sort(ups.begin(),ups.end(),[](int a,int b) {
			return W[a] > W[b];
		});
		
		v.clear();

		for(int j=0,k=0; j< tmp.size() || k< ups.size(); ) {
			if(j==tmp.size()) v.push_back(ups[k++]);
			else if(k==ups.size()) v.push_back(tmp[j++]);
			else if(W[tmp[j]]>=W[ups[k]]) v.push_back(tmp[j++]);
			else v.push_back(ups[k++]);
		}

		for(int j=0;j<cur2.size();j++) dontuse[cur2[j].u]=0;
 
 
 
	}
	for(int i=1;i<=K;i++)cout<<res[i]<<endl;
 
	
 
 
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   for(int j=0;j<cur1.size();j++) {
      |               ~^~~~~~~~~~~~
bridges.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |    for(int k=0;k<cur2.size();k++) {
      |                ~^~~~~~~~~~~~
bridges.cpp:139:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |    for(int k=0;k<cur2.size();k++) {
      |                ~^~~~~~~~~~~~
bridges.cpp:157:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |    for(int k=0;k<cur2.size();k++) {
      |                ~^~~~~~~~~~~~
bridges.cpp:175:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |   for(int j=0;j<cur2.size();j++) {
      |               ~^~~~~~~~~~~~
bridges.cpp:192:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |   for(int j=0,k=0; j< tmp.size() || k< ups.size(); ) {
      |                    ~^~~~~~~~~~~~
bridges.cpp:192:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |   for(int j=0,k=0; j< tmp.size() || k< ups.size(); ) {
      |                                     ~^~~~~~~~~~~~
bridges.cpp:193:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |    if(j==tmp.size()) v.push_back(ups[k++]);
      |       ~^~~~~~~~~~~~
bridges.cpp:194:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |    else if(k==ups.size()) v.push_back(tmp[j++]);
      |            ~^~~~~~~~~~~~
bridges.cpp:199:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |   for(int j=0;j<cur2.size();j++) dontuse[cur2[j].u]=0;
      |               ~^~~~~~~~~~~~
bridges.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
bridges.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   scanf("%d%d%d",&U,&V,&d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
bridges.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   scanf("%d%d%d",&t,&u,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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