Submission #1059041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059041		ZeroCool	Swapping Cities (APIO20_swap)	C++14	100 / 100	169 ms	74832 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int N =  5e5 + 20;
const int LOG = 21;

#define ar array

int p[N];
int nn;
vector<int> g[N];
bool ok[N];
int deg[N];

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

void join(int a,int b){
	deg[a]++, deg[b]++;
	if(deg[a] >= 3 || deg[b] >= 3)ok[nn] = 1;
	
	a = find(a), b = find(b);
	
	if(a == b)ok[nn] = 1;
	if(ok[a] || ok[b])ok[nn] = 1;
	
	p[a] = p[b] = p[nn] = nn;
	g[nn].push_back(a);
	if(a != b)g[nn].push_back(b);
	++nn;
}

int up[N][LOG];
int dp[N];
int dep[N];

void dfs(int x, int p,int lst = -1){
	//cout<<"->"<<x<<": "<<ok[x]<<endl;
	up[x][0] = p;
	for(int i = 1;i < LOG;i++)up[x][i] = up[up[x][i - 1]][i - 1];
	
	if(ok[x])lst = x;
	dp[x] = lst;
	
	for(auto u: g[x]){
		dep[u] = dep[x] + 1;
		dfs(u, x, lst);
	}
	//cout<<"<-"<<endl;
}

int lca(int a,int b){
	if(dep[a] < dep[b])swap(a, b);
	int k = dep[a] - dep[b];
	for(int i = 0;i < LOG;i++){
		if((1 << i) & k)a = up[a][i];
	}
	if(a == b)return a;
	for(int i = LOG - 1;i >= 0;i--){
		if(up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

ar<int, 3> ed[N];

int n;

void init(int _n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = _n;
	for(int i = 0;i < m;i++)ed[i] = {W[i], U[i], V[i]};
	sort(ed, ed + m);
	for(int i = 0;i < n;i++)p[i] = i;
	nn = n;
	for(int i = 0;i < m;i++)join(ed[i][1], ed[i][2]);
	dfs(nn-1, nn-1, -1);
}

int getMinimumFuelCapacity(int x, int y) {
	int l = lca(x, y);
	//cout<<x<<" "<<y<<": "<<l<<endl;
	if(dp[l] - n < 0)return -1;
	return ed[dp[l] - n][0];
}

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