Submission #328045

#	Time	Username	Problem	Language	Result	Execution time	Memory
328045		admin	Swapping Cities (APIO20_swap)	C++17	0 / 100	410 ms	524292 KiB

swap

#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
 
#include "swap.h"
 
 
int n,m;
int val=0;
vector<pair<int,pair<int,int>>> ed;
int par[100001];
int ss[100001];
int tt[100001];
int dd[100001];
multiset<int> xx[100001];
vector<int> comp[100001];
int ans[100001];
 
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
void upd(int x,int y){
	int stt=0;
 
	if(ss[x]>tt[x]-1){
		stt=1;
	}
	auto ee=xx[x].end();
	ee--;
	if(*ee>=3){
		stt=1;
	}
	if(stt){
		for(auto j:comp[x]){
			if(ans[j]==-1){
				ans[j]=y;
			}
		}
	}
}
int par2[100001];
int find2(int no){
	if(par2[no]==no){
		return no;
	}
	par2[no]=find2(par2[no]);
	return par2[no];
}
 
 
vector<pair<int,int>> adj[100001];
int par3[100001][20];
int mi[100001][20];
int lev[100001];
int dfs(int no,int parr=-1,int levv=0){
	lev[no]=levv;
	par3[no][0]=parr;
//	cout<<no<<":"<<endl;
	for(auto j:adj[no]){
 
		if(j.a==parr){
			continue;
		}
	//	cout<<no<<":"<<j.a<<endl;
		mi[j.a][0]=j.b;
		dfs(j.a,no,levv+1);
	}
}
 
void init(int nn, int mm,vector<int> aa,vector<int> bb,vector<int> cc) {
	m=mm;
	n=nn;
	for(int i=0;i<m;i++){
		ed.pb({cc[i],{aa[i],bb[i]}});
	}
	sort(ed.begin(),ed.end());
	for(int i=0;i<n;i++){
		par[i]=i;
		ss[i]=0;
		dd[i]=0;
		xx[i].clear();
		tt[i]=1;
		xx[i].insert(0);
		ans[i]=-1;
		adj[i].clear();
		comp[i].pb(i);
	}
	for(auto j:ed){
		int x=find(j.b.a);
		int y=find(j.b.b);
		if(x==y){
			ss[x]+=1;
			auto jj=xx[x].find(dd[j.b.a]);
			xx[x].erase(jj);
			dd[j.b.a]+=1;
			xx[x].insert(dd[j.b.a]);
 
			jj=xx[x].find(dd[j.b.b]);
			xx[x].erase(jj);
			dd[j.b.b]+=1;
			xx[x].insert(dd[j.b.b]);
			if(ans[x]==-1){
				upd(x,j.a);
			}
		}
		else{
			if(xx[x].size()<xx[y].size()){
				swap(x,y);
			}
			par[y]=x;
			for(auto jj:xx[y]){
				xx[x].insert(jj);
			}
			for(auto jj:comp[y]){
				comp[x].pb(jj);
				if(ans[x]!=-1 and ans[jj]==-1){
					ans[jj]=j.a;
				}
			}
			comp[y].clear();
			xx[y].clear();
			ss[x]+=ss[y]+1;
			tt[x]+=tt[y];
			
			auto jj=xx[x].find(dd[j.b.a]);
			xx[x].erase(jj);
			dd[j.b.a]+=1;
			xx[x].insert(dd[j.b.a]);
 
			jj=xx[x].find(dd[j.b.b]);
			xx[x].erase(jj);
			dd[j.b.b]+=1;
			xx[x].insert(dd[j.b.b]);
			if(ans[x]==-1){
				upd(x,j.a);
			}
		}
	}
	/*for(int i=0;i<n;i++){
		cout<<ans[i]<<":";
	}
	cout<<endl;*/
	for(int i=0;i<n;i++){
		par2[i]=i;
	}
	for(auto j:ed){
		int xx=find2(j.b.b);
		int yy=find2(j.b.a);
		if(xx!=yy){
			par2[xx]=yy;
		//	cout<<xx<<"   "<<yy<<endl;
			adj[j.b.a].pb({j.b.b,j.a});
			adj[j.b.b].pb({j.b.a,j.a});
		//	cout<<j.b.a<<","<<j.b.b<<endl;
		}
	}
	dfs(0);
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(par3[i][j-1]==-1){
				par3[i][j]=-1;
				continue;
			}
			par3[i][j]=par3[par3[i][j-1]][j-1];
			if(par3[i][j]!=-1){
				mi[i][j]=max(mi[i][j-1],mi[par3[i][j-1]][j-1]);
			}
		}
	}
}
 
int getMinimumFuelCapacity(int ac, int bc) {
	int aa=ac;
	int bb=bc;
	if(ans[aa]==-1 or ans[bb]==-1){
		return -1;
	}
	int tot=max(ans[aa],ans[bb]);
	if(lev[aa]>lev[bb]){
		swap(aa,bb);
	}
	int dif=lev[bb]-lev[aa];
	for(int j=0;j<19;j++){
		if((1<<j)&dif){
			tot=max(tot,mi[bb][j]);
			bb=par3[bb][j];
		}
	}
	if(bb==aa){
		return tot;
	}
	for(int j=19;j>=0;j--){
		if(par3[aa][j]!=par3[bb][j]){
			tot=max(tot,max(mi[aa][j],mi[bb][j]));
			aa=par3[aa][j];
			bb=par3[bb][j];
		}
	}
	tot=max(tot,max(mi[aa][0],mi[bb][0]));
 
 
 
	return tot;
	//return ac;
}

Compilation message (stderr)

swap.cpp: In function 'int dfs(int, int, int)':
swap.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
   76 | }
      | ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27