Submission #252718

#	Time	Username	Problem	Language	Result	Execution time	Memory
252718		kshitij_sodani	Bridges (APIO19_bridges)	C++14	14 / 100	3076 ms	20576 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<llo,llo>,pair<llo,llo>>> ed;
vector<pair<pair<llo,llo>,pair<llo,llo>>> ed2;

llo n,m,q;
vector<pair<llo,pair<llo,llo>>> qq;
const llo ss=10001;
vector<llo> kk;
vector<llo> mm;
llo vis[100001];
llo par[50001];
llo tt[50001];
llo find(llo no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
llo ans[100001];
llo vis2[100001];
vector<llo> adj[50001];
llo val[100001];
llo vis3[100001];
llo cot=0;
void dfs(llo no){
	vis3[no]=1;
	cot+=tt[no];
	for(auto j:adj[no]){
		if(vis3[j]==0){
			dfs(j);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<m;i++){
		llo 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(llo i=0;i<q;i++){
		llo t;
		cin>>t;
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		qq.pb({t,{aa,bb}});
	}
	for(llo i=0;i<=(q-1)/ss;i++){
		vector<pair<pair<llo,llo>,llo>> cur;
		for(llo 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});
			}
		}
		ed.clear();
		for(llo 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());


		sort(cur.begin(),cur.end());
		reverse(cur.begin(),cur.end());
		for(llo j=0;j<n;j++){
			par[j]=j;
			tt[j]=1;
		}
		llo ind=0;
		llo ind2=0;
		while(ind<cur.size() or ind2<ed.size()){
			llo 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<llo> nn;
				for(llo 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){
								llo x=find(ed2[qq[j].b.a].b.a);
								llo y=find(ed2[qq[j].b.a].b.b);
								adj[x].pb(y);
								adj[y].pb(x);
								nn.pb(x);
								nn.pb(y);
							}
						}
					}
				}
				for(llo 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){
								llo x=find(ed2[qq[j].b.a].b.a);
								llo y=find(ed2[qq[j].b.a].b.b);
								adj[x].pb(y);
								adj[y].pb(x);
								nn.pb(x);
								nn.pb(y);
							}
						}
					}
				}
				llo xx=find(cur[ind].a.b);
				cot=0;
				dfs(xx);
				ans[cur[ind].b]=cot;

				for(auto j:nn){
					vis3[j]=0;
					adj[j].clear();
				}
				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{
					llo x=find(ed[ind2].b.a);
					llo 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();
		for(llo j=ss*i;j<min(ss*(i+1),q);j++){
			if(qq[j].a==1){
				val[qq[j].b.a]=qq[j].b.b;
			}
		}
	}
	for(llo 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:92:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() or ind2<ed.size()){
         ~~~^~~~~~~~~~~
bridges.cpp:92:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() or ind2<ed.size()){
                           ~~~~^~~~~~~~~~
bridges.cpp:94:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind==cur.size()){
       ~~~^~~~~~~~~~~~
bridges.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(ind2==ed.size()){
            ~~~~^~~~~~~~~~~

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