Submission #1288763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288763		WH8	Swapping Cities (APIO20_swap)	C++17	53 / 100	195 ms	49984 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int maxn=100005, maxm=200005;

vector<vector<int>> up(maxn+maxm,vector<int>(20, -1));
vector<bool> able(maxn+maxm, 0);
vector<int> dep(maxn+maxm, 0),wei(maxn+maxm, 0), in(maxn, 0), clse(maxn+maxn, INT_MAX);
vector<pair<int,int>> ch(maxn+maxn, {-1, -1});

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

vector<int> p(maxn+maxm, -1);
int par(int x){
	if(p[x]==-1)return x;
	return p[x]=par(p[x]);
}

void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {
	vector<int> ord(M); iota(ord.begin(),ord.end(),0);
	sort(ord.begin(),ord.end(),[&](int a, int b){
		return W[a]<W[b];
	});
	int nw=N;
	for(int i=0;i<M;i++){
		int c=ord[i];
		int pa=par(U[c]), pb=par(V[c]);
		in[U[c]]++, in[V[c]]++;
		bool cable=able[pa] || able[pb] 
			|| (in[V[c]] >= 3) || (in[U[c]]>=3)
			|| (pa==pb);
		p[pa]=nw, p[pb]=nw;
		ch[nw].f=pa;
		up[pa][0]=nw, up[pb][0]=nw;
		if(pa!=pb)ch[nw].s=pb;
		wei[nw]=W[c];
		able[nw]=cable;
		
		nw++;
	}
	auto dfs=[&](auto && dfs, int x, int prv) -> void{
		if(able[x])prv=wei[x];
		clse[x]=prv;
		if(ch[x].f != -1){
			dep[ch[x].f]=dep[x]+1;
			dfs(dfs, ch[x].f, prv);
		}
		if(ch[x].s != -1){
			dep[ch[x].s]=dep[x]+1;
			dfs(dfs, ch[x].s, prv);
		}
	};
	dfs(dfs, nw-1, INT_MAX);
	for(int j=1;j<20;j++){
		for(int i=0;i<nw;i++){
			int prv=up[i][j-1];
			if(prv!=-1){
				up[i][j]=up[prv][j-1];
			}
		}
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int anc=lca(X, Y);
	if(clse[anc] == INT_MAX){
		return -1;
	}
	else return clse[anc];
}

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