| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 535970 | dutinmeow | Swapping Cities (APIO20_swap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#include "swap.h"
const int LOGN = 17;
struct node { int par, val, siz; bool lin; };
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);
}
);
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, 1, 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, T[up].siz + T[vp].siz, true);
if (T[up].siz > 1)
ep[u] = false;
if (T[vp].siz > 1)
ep[v] = false;
} else {
T[up].par = T[vp].par = T.size();
T.emplace_back(c, w, T[up].siz + T[vp].siz, false);
}
} else if (T[up].lin) {
T[up].par = c;
T.emplace_back(c, w, T[up].siz + T[vp].siz, 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];
}
}