Submission #1208468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208468		k1r1t0	Swapping Cities (APIO20_swap)	C++20	100 / 100	184 ms	53300 KiB

swap

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 310000;
const int LOGN = 20;

int n, m, p[N], s[N], es[N][2], t[N], vw[N], depth[N], jmp[N][LOGN];
bool good[N], path[N];
vector<array<int, 3>> edge;
vector<int> g[N];

void init_dsu() {
	for (int i = 1; i <= n; i++) {
		path[i] = true;
		es[i][0] = es[i][1] = p[i] = t[i] = i;
	}
}

int getp(int x) {
	return x == p[x] ? x : p[x] = getp(p[x]);
}

void unite(int u, int v, int w, int k) {
	int a = getp(u);
	int b = getp(v);
	if (a == b) {
		g[k].push_back(t[a]);
		path[a] = false;
	} else {
		g[k].push_back(t[a]);
		g[k].push_back(t[b]);
		if (s[a] < s[b]) swap(a, b);
		s[a] += s[b];
		p[b] = a;
		if (!path[a] || !path[b])
			path[a] = false;
		else {
			if ((u == es[a][0] || u == es[a][1]) && (v == es[b][0] || v == es[b][1])) {
				int x = es[a][0] + es[a][1] - u;
				int y = es[b][0] + es[b][1] - v;
				es[a][0] = x;
				es[a][1] = y;
			} else path[a] = false;
		}
	}
	good[k] = !path[a];
	vw[k] = w;
	t[a] = k;
}

void dfs(int v, int p = -1) {
	depth[v] = (p == -1 ? 0 : depth[p] + 1);
	jmp[v][0] = (p == -1 ? v : p);
	for (int k = 1; k < LOGN; k++)
		jmp[v][k] = jmp[jmp[v][k - 1]][k - 1];
	for (int u : g[v])
		dfs(u, v);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	for (int i = 0; i < m; i++)
		edge.push_back({W[i], U[i] + 1, V[i] + 1});
	sort(begin(edge), end(edge));
	init_dsu();
	for (int i = 0; i < m; i++)
		unite(edge[i][1], edge[i][2], edge[i][0], n + 1 + i);
	dfs(n + m);
}

int lca(int a, int b) {
	if (depth[a] < depth[b])
		swap(a, b);
	for (int k = LOGN - 1; k >= 0; k--)
		if (depth[a] - (1 << k) >= depth[b])
			a = jmp[a][k];
	if (a == b) return a;
	for (int k = LOGN - 1; k >= 0; k--)
		if (jmp[a][k] != jmp[b][k]) {
			a = jmp[a][k];
			b = jmp[b][k];
		}
	return jmp[a][0];
}

int getMinimumFuelCapacity(int X, int Y) {
	X++; Y++;
	int L = lca(X, Y);
	if (good[L]) return vw[L];
	for (int k = LOGN - 1; k >= 0; k--)
		if (!good[jmp[L][k]])
			L = jmp[L][k];
	L = jmp[L][0];
	if (good[L]) return vw[L];
	return -1;
}

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