Submission #938192

#	Time	Username	Problem	Language	Result	Execution time	Memory
938192		IBory	Swapping Cities (APIO20_swap)	C++17	100 / 100	289 ms	69136 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 400004;
int N, M, R[MAX], D[MAX], H[MAX], S[MAX], P[19][MAX];
bool T[MAX], C[MAX], isLine;
vector<tuple<int, int, int>> E;
vector<int> G[MAX];

int Find(int n) {
	if (n == R[n]) return n;
	return R[n] = Find(R[n]);
}

void DFS(int cur, int prev) {
	H[cur] = H[prev] + 1;
	P[0][cur] = prev;
	for (int next : G[cur]) DFS(next, cur);
}

int LCA(int a, int b) {
	if (H[a] > H[b]) swap(a, b);
	for (int i = 18; i >= 0; --i) if ((H[b] - H[a]) & (1 << i)) b = P[i][b];
	if (a == b) return a;
	for (int i = 18; i >= 0; --i) if (P[i][a] != P[i][b]) a = P[i][a], b = P[i][b];
	return P[0][a];
}

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());

	iota(R, R + MAX, 0);
	memset(D, 0, sizeof(D));
	int node = N;
	for (auto [w, a, b] : E) {
		int ra = Find(a), rb = Find(b);
		S[node] = w;
		T[node] = (T[ra] || T[rb] || ++D[a] >= 3 || ++D[b] >= 3);
		C[node] = (C[ra] || C[rb] || ra == rb);
		G[node].push_back(ra);
		if (ra != rb) G[node].push_back(rb);
		R[ra] = R[rb] = node;
		node++;
	}

	DFS(node - 1, node - 1);
	for (int n = 1; n < 19; ++n) for (int i = 0; i < node; ++i) P[n][i] = P[n - 1][P[n - 1][i]];
}
 
int getMinimumFuelCapacity(int x, int y) {
	if (isLine) return -1;
 
	int c = LCA(x, y);
	for (int i = 18; i >= 0; --i) {
		int p = P[i][c];
		if (!T[p] && !C[p]) c = p;
	}
	if (!T[c] && !C[c]) c = P[0][c];

	return S[c];
}

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