Submission #338618

#	Time	Username	Problem	Language	Result	Execution time	Memory
338618		nandonathaniel	Swapping Cities (APIO20_swap)	C++14	100 / 100	502 ms	60892 KiB

swap

#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
const int MAXN=100005,MAXM=200005,LOG=19;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
int par[MAXN+MAXM],deg[MAXN],cost[MAXN+MAXM],N,depth[MAXN+MAXM],pa[LOG][MAXN+MAXM];
bool bisaswap[MAXN+MAXM];
vector<piii> edges;
vector<int> adj[MAXN+MAXM];

int find(int x){
	if(par[x]==x)return x;
	return par[x]=find(par[x]);
}

int LCA(int u,int v){
	if(depth[u]<depth[v])swap(u,v);
	int diff=depth[u]-depth[v];
	for(int i=LOG-1;i>=0;i--){
		if(diff & (1<<i))u=pa[i][u];
	}
	if(u==v)return u;
	for(int i=LOG-1;i>=0;i--){
		if(pa[i][u]!=pa[i][v]){
			u=pa[i][u];
			v=pa[i][v];
		}
	}
	return pa[0][u];
}

void dfs(int now){
	for(auto nxt : adj[now]){
		pa[0][nxt]=now;
		for(int i=1;i<LOG;i++)pa[i][nxt]=pa[i-1][pa[i-1][nxt]];
		depth[nxt]=depth[now]+1;
		dfs(nxt);
	}
}

void init(int n, int m,
          vector<int> U, vector<int> V, vector<int> W) {
    N=n;
	for(int i=0;i<m;i++){
		U[i]++;V[i]++;
		edges.push_back({W[i],{U[i],V[i]}});
	}
	for(int i=1;i<=N;i++){
		par[i]=i;
		deg[i]=0;
		bisaswap[i]=false;
	}
	sort(edges.begin(),edges.end());
	for(auto isi : edges){
		int ortua=find(isi.se.fi),ortub=find(isi.se.se);
		deg[isi.se.fi]++;
		deg[isi.se.se]++;
		N++;
		par[N]=N;
		par[ortua]=N;
		par[ortub]=N;
		if(ortua==ortub){
			bisaswap[N]=true;
		}
		else if(bisaswap[ortua] || bisaswap[ortub] || deg[isi.se.fi]>=3 || deg[isi.se.se]>=3){
			bisaswap[N]=true;
		}
		cost[N]=isi.first;
		adj[N].push_back(ortua);
		if(ortua!=ortub)adj[N].push_back(ortub);
	}
	dfs(N);
}

int getMinimumFuelCapacity(int X, int Y) {
	if(!bisaswap[N])return -1;
	X++;Y++;
	int anc=LCA(X,Y);
	if(bisaswap[anc])return cost[anc];
	for(int i=LOG-1;i>=0;i--){
		if((1<<i)>depth[anc])continue;
		if(!bisaswap[pa[i][anc]]){
			anc=pa[i][anc];
		}
	}
	return cost[pa[0][anc]];
}

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