Submission #1212044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212044		dubabuba	Swapping Cities (APIO20_swap)	C++20	0 / 100	85 ms	36956 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;
const int mxn = 2e5 + 10;

#define ff first
#define ss second
#define MP make_pair
typedef pair<int, int> pii;

vector<int> adj[mxn];
vector<pair<int, pii>> edges;
int par[mxn], val[mxn], n, m;
int cyc[mxn], anc[LOG][mxn];
int CNT;

int parent(int u) { return par[u] < 0 ? u : par[u] = parent(par[u]); }
void unite(int u, int v, const int w, int &cnt) {
	u = parent(u);
	v = parent(v);

	if(u == v) {
		cyc[u] = 1;
		return;
	}

	// par[cnt] += par[u];
	// par[cnt] += par[v];
	val[cnt] = w;
	par[u] = par[v] = cnt;
	cyc[cnt] = cyc[u] | cyc[v];
	anc[0][u] = anc[0][v] = cnt;
	adj[cnt].push_back(u);
	adj[cnt].push_back(v);
	cnt++;
}

int lvl[mxn];
void dfs(int u, int p = -1) {
	// cout << u << ": " << val[u] << ", " << cyc[u] << endl;
	for(int v : adj[u]) {
		lvl[v] = lvl[u] + 1;
		// cout << u << " -> " << v << endl;
		dfs(v, u);
		if(cyc[v]) assert(cyc[u]);
	}
}

int LCA(int u, int v) {
	if(lvl[u] < lvl[v]) swap(u, v);
	int JUMP = lvl[u] - lvl[v];
	for(int i = 0; i < LOG; i++)
		if(JUMP & (1 << i)) {
			u = anc[i][u];
		}

	assert(lvl[u] == lvl[v]);
	if(u == v) return u;
	for(int i = LOG - 1; i >= 0; i--)
	if(anc[i][u] != anc[i][v]) {
		u = anc[i][u];
		v = anc[i][v];
	}
	return anc[0][u];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	for(int i = 0; i < M; i++) {
		const int &u = U[i];
		const int &v = V[i];
		const int &w = W[i];
		edges.emplace_back(w, MP(u, v));
	}
	n = N, m = M;

	memset(par, -1, sizeof par);
	for(int i = 0; i < LOG; i++)
		memset(anc[i], -1, sizeof anc[i]);

	int cnt = N;
	sort(edges.begin(), edges.end());
	for(const auto &p : edges) {
		unite(p.ss.ff, p.ss.ss, p.ff, cnt);
	}

	assert(par[cnt - 1] == -1);
	assert(cnt == 2 * n - 1);

	for(int k = 1; k < LOG; k++)
	for(int i = 0; i < cnt; i++) {
		int j = anc[k - 1][i];
		if(j > -1) {
			anc[k][i] = anc[k - 1][j];
		}
	}

	dfs(cnt - 1);
	CNT = cnt;
}

int getMinimumFuelCapacity(int X, int Y) {
	if(X == Y) return -1;
	if(cyc[CNT - 1] == 0) return -1;
	int A = LCA(X, Y);
	if(cyc[A] == 1) return val[A];
	for(int i = LOG - 1; i >= 0; i--) {
		int B = anc[i][A];
		if(B > -1 && cyc[B] == 0) {
			A = B;
		}
	}
	A = anc[0][A];
	return val[A];
}

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3

3
1 2
2 4
0 1

*/

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