Submission #293977

#	Time	Username	Problem	Language	Result	Execution time	Memory
293977		oolimry	Swapping Cities (APIO20_swap)	C++14	100 / 100	524 ms	30436 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef pair<int,int> ii;
const int inf = 1023456789;

int n, newNode;

namespace ufds{
	int p[200005];

	void init(){
		for(int i = 0;i < 2*n;i++) p[i] = i;
	}

	int findSet(int u){
		if(u == p[u]) return u;
		else return p[u] = findSet(p[u]);
	}		

	bool unionSet(int u, int v){
		u = findSet(u), v = findSet(v);
		if(u == v) return false;
		
		if(u > v) swap(u, v);
		p[u] = v;
		return true;
	}
}

struct edge{ int u, v, w; };
vector<edge> edges;

int maxEdge[200005];
int minWork[200005];
int L[200005];
int R[200005];
int deg[200005];
int p[200005][19];
int depth[200005];

void dfs0(int u){
	if(L[u] == R[u] && L[u] == 0) return;
		
	depth[L[u]] = depth[u] + 1;
	depth[R[u]] = depth[u] + 1;
	dfs0(L[u]); dfs0(R[u]);
}

void dfs1(int u){
	if(L[u] == R[u] && L[u] == 0) return;
	
	dfs1(L[u]); dfs1(R[u]);
	
	minWork[u] = min(minWork[u], minWork[L[u]]); ///pass up to parent
	minWork[u] = min(minWork[u], minWork[R[u]]);
}

void dfs2(int u){
	if(L[u] == R[u] && L[u] == 0) return;
	
	minWork[L[u]] = min(minWork[u], minWork[L[u]]); ///pass down to children
	minWork[R[u]] = min(minWork[u], minWork[R[u]]);
	
	dfs2(L[u]); dfs2(R[u]);
}

int LCA(int u, int v){
	if(depth[u] < depth[v]) swap(u, v);
	
	for(int k = 18;k >= 0;k--){
		int newU = p[u][k];
		if(depth[newU] >= depth[v]) u = newU;
	}
	
	for(int k = 18;k >= 0;k--){
		int newU = p[u][k], newV = p[v][k];
		if(newU != newV){
			u = newU;
			v = newV;
		}
	}
	return p[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N; newNode = n;
	
	for(int i = 0;i < M;i++) edges.push_back({U[i], V[i], W[i]});
	
	ufds::init();
	fill(minWork, minWork+2*n, inf);
	
	sort(all(edges), [&](edge a, edge b){ return a.w < b.w; });
	
	vector<edge> cycle;
	for(edge e : edges){
		deg[e.u]++;
		deg[e.v]++;
		if(deg[e.u] >= 3) minWork[e.u] = min(e.w, minWork[e.u]);
		if(deg[e.v] >= 3) minWork[e.v] = min(e.w, minWork[e.v]);
		
		int u = ufds::findSet(e.u), v = ufds::findSet(e.v);
		if(u != v){
			L[newNode] = u;
			R[newNode] = v;
			ufds::unionSet(newNode, u);
			ufds::unionSet(newNode, v);
			maxEdge[newNode] = e.w;
			
			p[u][0] = newNode;
			p[v][0] = newNode;
			
			newNode++;
		}
		else cycle.push_back(e);
	}
	
	n = newNode;
	p[n-1][0] = -1;
	
	for(int k = 1;k <= 18;k++){
		for(int i = 0;i < n;i++){
			if(p[i][k-1] == -1) p[i][k] = -1;
			else p[i][k] = p[p[i][k-1]][k-1];
		}
	}
	
	dfs0(n-1);

	for(edge e : cycle){
		int u = e.u, v = e.v;
		int lca = LCA(u, v);
		minWork[lca] = min(e.w, minWork[lca]);
	}
	
	dfs1(n-1);
	
	for(int i = 0;i < n;i++) minWork[i] = max(minWork[i], maxEdge[i]);
	
	dfs2(n-1); 
}

int getMinimumFuelCapacity(int X, int Y){
	
	int lca = LCA(X, Y);
	//cout << X << " " << Y << " " << lca << "\n";
	
	int ans = max(minWork[lca], maxEdge[lca]);
	if(ans == inf) ans = -1;
	return ans;
}

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