Submission #1181033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181033		stdfloat	Swapping Cities (APIO20_swap)	C++20	100 / 100	329 ms	66208 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
// #include "grader.cpp"
using namespace std;

#define ff	first
#define ss	second
#define pii	pair<int, int>

vector<int> p, W, H;

vector<bool> swp;

vector<vector<int>> E, sp;

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

void dfs(int x) {
	for (auto i : E[x]) {
		H[i] = H[x] + 1;
		dfs(i);
	}
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
	vector<pair<int, pii>> edg;
	for (int i = 0; i < m; i++)
		edg.push_back({w[i], {u[i], v[i]}});

	sort(edg.begin(), edg.end());

	E.assign(n + m, {});
	swp.assign(n + m, false);
	sp.assign(n + m, vector<int>(20, -1));

	p = W = vector<int>(n + m, 0);
	iota(p.begin(), p.end(), 0);

	int ind = n;
	vector<int> cnt(n);
	for (auto [w, i] : edg) {
		int x = fnd(i.ff), y = fnd(i.ss);

		cnt[i.ff]++; cnt[i.ss]++;

		E[ind].push_back(x);
		if (x != y) E[ind].push_back(y);

		p[x] = p[y] = sp[x][0] = sp[y][0] = ind;

		W[ind] = w;
		swp[ind] = (x == y || swp[x] || swp[y] || 2 < max(cnt[i.ff], cnt[i.ss]));
	
		ind++;
	}

	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n + m; j++)
			if (~sp[j][i - 1]) sp[j][i] = sp[sp[j][i - 1]][i - 1];
	}

	H.assign(n + m, 0);
	dfs(ind - 1);
}

int getMinimumFuelCapacity(int s, int t) {
	if (H[s] < H[t]) swap(s, t);

	for (int i = 19; i >= 0; i--)
		if (H[s] - (1 << i) >= H[t]) s = sp[s][i];

	for (int i = 19; i >= 0; i--) {
		if (sp[s][i] != sp[t][i]) {
			s = sp[s][i]; t = sp[t][i];
		}
	}

	s = sp[s][0];

	if (swp[s]) return W[s];

	for (int i = 19; i >= 0; i--) {
		if (~sp[s][i] && !swp[sp[s][i]]) s = sp[s][i];
	}

	return (!~sp[s][0] ? -1 : W[sp[s][0]]);
}

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