Submission #535983

#	Time	Username	Problem	Language	Result	Execution time	Memory
535983		dutinmeow	Swapping Cities (APIO20_swap)	C++17	53 / 100	2074 ms	34832 KiB

swap

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

//#include "swap.h"

const int LOGN = 19;

vector<int> dep, val;
vector<bool> lin;
vector<array<int, LOGN>> anc;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	vector<tuple<int, int, int>> E(M);
	for (int i = 0; i < M; i++) 
		E[i] = {U[i], V[i], W[i]};
	sort(E.begin(), E.end(), 
		[](const auto &a, const auto &b) {
			return get<2>(a) < get<2>(b);
		}
	);

	struct node { 
		int par, val; bool lin;
		node() = default;
		node(int _par, int _val, bool _lin) : par(_par), val(_val), lin(_lin) {}
	};

	vector<node> T; T.reserve(N + M);
	vector<bool> ep(N);
	vector<int> rt(N);

	for (int i = 0; i < N; i++) {
		T.emplace_back(i, 0, true);
		ep[i] = true;
		rt[i] = i;
	}

	for (auto [u, v, w] : E) {
		while (rt[u] != T[rt[u]].par)
			rt[u] = T[rt[u]].par;
		int up = rt[u];
		while (rt[v] != T[rt[v]].par)
			rt[v] = T[rt[v]].par;
		int vp = rt[v];

		int c = T.size();
		if (up != vp) {
			if (T[up].lin && T[vp].lin && ep[u] && ep[v]) {
				T[up].par = T[vp].par = c;
				T.emplace_back(c, w, true);
				if (up != u)
					ep[u] = false;
				if (vp != v)
					ep[v] = false;
			} else {
				T[up].par = T[vp].par = T.size();
				T.emplace_back(c, w, false);
			}
		} else if (T[up].lin) {
			T[up].par = c;
			T.emplace_back(c, w, false);
		}

		/*
		cout << "edge " << u << ' ' << v << ' ' << w << '\n';
		for (int i = 0; i < T.size(); i++) 
			cout << i << " : " << T[i].par << ' ' << T[i].val << ' ' << (T[i].lin ? "line" : "not line") << '\n';
		cout << '\n';
		*/
	}

	int S = T.size();
	anc.resize(S);
	dep.resize(S);
	val.resize(S);
	lin.resize(S);
	vector<vector<int>> tree(S);
	for (int i = 0; i < S; i++) {
		anc[i][0] = T[i].par;
		val[i] = T[i].val;
		lin[i] = T[i].lin;
		if (i != T[i].par)
			tree[T[i].par].push_back(i);
	}
	for (int k = 1; k < LOGN; k++)
		for (int i = 0; i < S; i++)
			anc[i][k] = anc[anc[i][k - 1]][k - 1];

	const auto dfs = [&](const auto &self, int u) -> void {
		for (int v : tree[u]) {
			dep[v] = dep[u] + 1;
			self(self, v);
		}
	};

	for (int i = 0; i < S; i++) 
		if (i == T[i].par) {
			dep[i] = 0;
			dfs(dfs, i);
		}
}

int getMinimumFuelCapacity(int u, int v) {
	if (dep[u] > dep[v])
		swap(u, v);
	for (int k = LOGN - 1; k >= 0; k--)
		if ((dep[v] - dep[u]) >> k & 1)
			v = anc[v][k];
	//assert(dep[u] == dep[v]);
	if (u != v) {
		for (int k = LOGN - 1; k >= 0; k--)
			if (anc[u][k] != anc[v][k])
				u = anc[u][k], v = anc[v][k];
		u = anc[u][0], v = anc[v][0];
		if (u != v)
			return -1;
	}

	if (!lin[u]) 
		return val[u];
	for (int k = LOGN - 1; k >= 0; k--)
		if (lin[anc[u][k]])
			u = anc[u][k];
	u = anc[u][0];
	if (lin[u]) {
		return -1;
	} else {
		return val[u];
	}
}

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