Submission #252743

#	Time	Username	Problem	Language	Result	Execution time	Memory
252743		kshitij_sodani	Bridges (APIO19_bridges)	C++14	100 / 100	2482 ms	28044 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
vector<pair<pair<int,int>,pair<int,int>>> ed;
vector<pair<pair<int,int>,pair<int,int>>> ed2;
vector<pair<pair<int,int>,pair<int,int>>> ed3;
vector<pair<pair<int,int>,pair<int,int>>> ed4;

int n,m,q;
vector<pair<int,pair<int,int>>> qq;
const int ss=600;
vector<int> kk;
vector<int> mm;
int vis[100001];
int par[50001];
int tt[50001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int ans[100001];
int vis2[100001];
vector<int> adj[50001];
int val[100001];
int vis3[100001];
int cot=0;
void dfs(int no){
	vis3[no]=1;
	cot+=tt[no];
	for(auto j:adj[no]){
		if(vis3[j]==0){
			dfs(j);
		}
	}
}
int vis4[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		ed2.pb({{cc,i},{aa,bb}});
		val[i]=cc;
	}
	/*sort(cc.begin(),cc.end());
	reverse(cc.begin(),cc.end());*/
	cin>>q;
	for(int i=0;i<q;i++){
		int t;
		cin>>t;
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		qq.pb({t,{aa,bb}});
	}
	ed=ed2;
	sort(ed.begin(),ed.end());
	reverse(ed.begin(),ed.end());

	set<int> rep;
	for(int i=0;i<=(q-1)/ss;i++){
		//cout<<i<<":::"<<endl;
		vector<pair<pair<int,int>,int>> cur;
		for(auto j:rep){
			vis4[j]=1;
			ed3.pb({{val[j],j},ed2[j].b});
		}
		sort(ed3.begin(),ed3.end());
		reverse(ed3.begin(),ed3.end());
		int ind3=0;
		int ind4=0;
		while(ind3<ed3.size() or ind4<ed.size()){
			int st=1;
			if(ind3==ed3.size()){
				st=0;
			}
			else if(ind4==ed.size()){

			}
			else{
				if(ed[ind4].a.a>=ed3[ind3].a.a){
					st=0;
				}
			}
			if(st){
				ed4.pb(ed3[ind3]);
				ind3++;
			}
			else{
				if(vis4[ed[ind4].a.b]==0){
					ed4.pb(ed[ind4]);
				}
				ind4++;
			}
		}



		ed3.clear();
		for(auto j:rep){
			vis4[j]=0;
		}
		ed=ed4;
		ed4.clear();
		/*ed.clear();*/
		/*for(int j=0;j<m;j++){
			ed.pb({{val[ed2[j].a.b],ed2[j].a.b},ed2[j].b});
		}*/
		/*sort(ed.begin(),ed.end());
		reverse(ed.begin(),ed.end());
*/
		for(int j=ss*i;j<min(ss*(i+1),q);j++){
			if(qq[j].a==1){
				vis[qq[j].b.a]=1;
				kk.pb(qq[j].b.a);
			//	cout<<qq[j].b.a<<endl;
			}
			else{
				cur.pb({{qq[j].b.b,qq[j].b.a},j});
			}
		}

		sort(cur.begin(),cur.end());
		reverse(cur.begin(),cur.end());
		for(int j=0;j<n;j++){
			par[j]=j;
			tt[j]=1;
		}
		int ind=0;
		int ind2=0;
		while(ind<cur.size() or ind2<ed.size()){
			int st=1;//1 denotes take cur
			if(ind==cur.size()){
				st=0;
			}
			else if(ind2==ed.size()){
			}
			else{
				if(ed[ind2].a.a>=cur[ind].a.a){
					st=0;
				}
			}
			if(st){
				//take cur
				vector<int> nn;
				for(int j=cur[ind].b;j>=ss*i;j--){
					if(qq[j].a==1){
						if(vis2[qq[j].b.a]==0){
							mm.pb(qq[j].b.a);
							vis2[qq[j].b.a]=1;
							if(qq[j].b.b>=cur[ind].a.a){
								int x=find(ed2[qq[j].b.a].b.a);
								int y=find(ed2[qq[j].b.a].b.b);
								adj[x].pb(y);
								adj[y].pb(x);
								nn.pb(x);
								nn.pb(y);
							}
						}
					}
				}
				for(int j=cur[ind].b;j<min(ss*(i+1),q);j++){
					if(qq[j].a==1){
						if(vis2[qq[j].b.a]==0){
							mm.pb(qq[j].b.a);
							vis2[qq[j].b.a]=1;
							if(val[qq[j].b.a]>=cur[ind].a.a){
								int x=find(ed2[qq[j].b.a].b.a);
								int y=find(ed2[qq[j].b.a].b.b);
								adj[x].pb(y);
								adj[y].pb(x);
							//	cout<<x<<"//"<<y<<endl;
								nn.pb(x);
								nn.pb(y);
							}
						}
					}
				}
				int xx=find(cur[ind].a.b);
			//	cout<<xx<<endl;
				cot=0;
			//	cout<<cur[ind].b<<"/"<<endl;
				dfs(xx);
				ans[cur[ind].b]=cot;

				for(auto j:nn){
					vis3[j]=0;
					adj[j].clear();
				}
				vis3[xx]=0;
				for(auto j:mm){
					vis2[j]=0;
				}
				nn.clear();
				mm.clear();
				ind++;
			}
			else{
				//add edge
			///	cout<<1<<":"<<ed[ind2].a.a<<","<<ed[ind2].a.b<<","<<ed[ind2].b.a<<","<<ed[ind2].b.b<<endl;
				if(vis[ed[ind2].a.b]){
				}
				else{
					int x=find(ed[ind2].b.a);
					int y=find(ed[ind2].b.b);
				//	cout<<ed[ind2].b.b<<":"<<ed[ind2].b.a<<endl;
					if(x!=y){
						par[y]=x;
						tt[x]+=tt[y];
					}
				}
				ind2++;
			}
		}
		for(auto j:kk){
			vis[j]=0;
		}
		kk.clear();

		rep.clear();
		for(int j=ss*i;j<min(ss*(i+1),q);j++){
			if(qq[j].a==1){
				val[qq[j].b.a]=qq[j].b.b;
				rep.insert(qq[j].b.a);
			}
		}
	}
	for(int i=0;i<q;i++){
		if(qq[i].a==2){
			cout<<ans[i]<<endl;
		}
	}






	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:83:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind3<ed3.size() or ind4<ed.size()){
         ~~~~^~~~~~~~~~~
bridges.cpp:83:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind3<ed3.size() or ind4<ed.size()){
                            ~~~~^~~~~~~~~~
bridges.cpp:85:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind3==ed3.size()){
       ~~~~^~~~~~~~~~~~
bridges.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(ind4==ed.size()){
            ~~~~^~~~~~~~~~~
bridges.cpp:142:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() or ind2<ed.size()){
         ~~~^~~~~~~~~~~
bridges.cpp:142:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() or ind2<ed.size()){
                           ~~~~^~~~~~~~~~
bridges.cpp:144:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind==cur.size()){
       ~~~^~~~~~~~~~~~
bridges.cpp:147:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(ind2==ed.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