Submission #684001

#	Time	Username	Problem	Language	Result	Execution time	Memory
684001		thiago_bastos	Swapping Cities (APIO20_swap)	C++17	13 / 100	127 ms	12168 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

int par[MAXN], depth[MAXN], t[MAXN], third[MAXN], deg[MAXN];

int findSet(int u) {
	return u == par[u] ? u : findSet(par[u]);
}

int h(int u) {
	return u == par[u] ? 0 : 1 + h(par[u]);
}

bool merge(int u, int v, int w) {
	u = findSet(u);
	v = findSet(v);
	if(u == v) return false;
	if(depth[u] > depth[v]) swap(u, v);
	par[u] = v;
	depth[v] += depth[u] == depth[v];	
	third[v] = min(third[v], third[u]);
	t[u] = w;
	return true;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	for(int i = 0; i < N; ++i) {
		par[i] = i;
		third[i] = INT_MAX;
	}
	vector<tuple<int, int, int>> edge(M);
	for(int i = 0; i < M; ++i) edge[i] = {W[i], U[i], V[i]};
	sort(edge.begin(), edge.end());
	for(auto [w, u, v] : edge) {
		++deg[u], ++deg[v];
		bool e = merge(u, v, w);
		if(!e || max(deg[u], deg[v]) > 2) {
			int x = findSet(u);
			third[x] = min(third[x], w);
		}
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int Z = findSet(X);
	int hx = h(X), hy = h(Y), ans = third[Z];
	if(ans == INT_MAX) return -1;
	while(hx != hy) {
		if(hx > hy) {
			ans = max(ans, t[X]);		
			X = par[X];
			--hx;
		} else {
			ans = max(ans, t[Y]);
			Y = par[Y];
			--hy;
		}
	}
	while(X != Y) {
		ans = max(ans, max(t[X], t[Y]));
		X = par[X];
		Y = par[Y];
	}
	return ans;
}

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