Submission #938183

#	Time	Username	Problem	Language	Result	Execution time	Memory
938183		IBory	Swapping Cities (APIO20_swap)	C++17	37 / 100	2065 ms	50368 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 200007;
int N, M, Z[MAX], D[MAX];
bool isLine;
vector<tuple<int, int, int>> E;
vector<pii> R[MAX], T[MAX], C[MAX];

void Clear() {
	for (int i = 0; i < MAX; ++i) {
		R[i].clear();
		T[i].clear();
		C[i].clear();
		R[i].emplace_back(-1, i);
		T[i].emplace_back(-1, 0);
		C[i].emplace_back(-1, 0);
	}
	memset(D, 0, sizeof(D));
	fill(Z, Z + MAX, 1);
}

int Find(int n, int t) {
	int tr = R[n].back().second;
	if (T[n].back().second && !T[tr].back().second) T[tr].emplace_back(t, 1);
	if (C[n].back().second && !C[tr].back().second) C[tr].emplace_back(t, 1);
	if (n == tr) return n;
	int r = Find(tr, t);
	if (R[n].back().second != r) R[n].emplace_back(t, r);
	return R[n].back().second;
}

void Union(int a, int b, int t) {
	if (Z[a] > Z[b]) swap(a, b);
	if (++D[a] == 3 && !T[a].back().second) T[a].emplace_back(t, 1);
	if (++D[b] == 3 && !T[b].back().second) T[b].emplace_back(t, 1);
	a = Find(a, t), b = Find(b, t);
	if (a == b) {
		if (!C[a].back().second) C[a].emplace_back(t, 1);
		return;
	}
	Z[b] += Z[a];
	R[a].emplace_back(t, b);
	if (T[a].back().second && !T[b].back().second) T[b].emplace_back(t, 1);
	if (C[a].back().second && !C[b].back().second) C[b].emplace_back(t, 1);
}

int TFind(vector<pii>& S, int t) {
	auto it = upper_bound(S.begin(), S.end(), pii{t, 1 << 30});
	return (*--it).second;
}

int getMinimumFuelCapacity(int x, int y) {
	if (isLine) return -1;

	int l = -1, r = M - 1;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		int rx = x, ry = y;
		while (1) {
			int t = TFind(R[rx], mid);
			if (rx == t) break;
			rx = t;
		}
		while (1) {
			int t = TFind(R[ry], mid);
			if (ry == t) break;
			ry = t;
		}
		bool ok = (rx == ry && (TFind(T[rx], mid) || TFind(C[rx], mid)));
		(ok ? r : l) = mid;
	}

	auto [ans, a, b] = E[r];
	return ans;
}

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) {
		E.emplace_back(W[i], U[i], V[i]);
		D[U[i]]++;
		D[V[i]]++;
	}
	if (N == M + 1 && *max_element(D, D + MAX) <= 2) isLine = 1;
	sort(E.begin(), E.end());

	Clear();
	for (int i = 0; i < M; ++i) {
		auto [_, a, b] = E[i];
		Union(a, b, i);
	}
}

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