| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 983555 | RakhimovAmir | Swapping Cities (APIO20_swap) | C++14 | 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 "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct edge {
ll w, x, y;
};
const ll N = 1e5 + 100, M = 30;
vector<pair<ll, ll>> g[N];
vector<edge> edges;
ll prt[N], a[N], b[N], p[N][M], mx[N][M], tin[N], tout[N], tt;
bool fl[N], visited[N];
vector<ll> v[N];
bool cmp(edge a, edge b) {
return a.w < b.w;
}
ll findParent(ll x) {
if (prt[x] == x)
return x;
return prt[x] = findParent(prt[x]);
}
void addEdge(ll x, ll y, ll w) {
g[x].push_back({w, y});
g[y].push_back({w, x});
}
void merge(ll x, ll y, ll w) {
ll X = prt[x], Y = prt[y];
if (X == Y) {
if (!fl[X])
return;
fl[X] = 0;
for (auto i : v[X]) {
if (i != X) {
addEdge(X, i, w);
}
}
return;
}
if (v[Y].size() > v[X].size()) {
swap(x, y);
swap(X, Y);
}
for (auto i : v[Y]) {
v[X].push_back(i);
}
prt[Y] = X;
if (!fl[X] || !fl[Y] || (x != a[X] && x != b[X]) || (y != a[Y] && y != b[Y])) {
fl[X] = 0;
addEdge(X, Y, w);
return;
} else {
if (x == a[X]) {
if (y == b[Y])
a[X] = a[Y];
else
a[X] = b[Y];
}
else {
if (y == b[Y])
b[X] = a[Y];
else
b[X] = b[Y];
}
}
}
void dfs(ll x, ll par, ll w) {
tin[x] = ++tt;
visited[x] = 1;
for (auto to : g[x]) {
if (!visited[to.second])
dfs(to.second, x, to.first);
}
p[x][0] = par;
mx[x][0] = w;
for (ll i = 1; i < M; i++) {
p[x][i] = p[p[x][i - 1]][i - 1];
mx[x][i] = max(mx[x][i - 1], mx[p[x][i - 1]][i - 1]);
// cout << mx[x][i] << " " << x << " " << i << "\n";
}
tout[x] = tt;
}
ll ispr(ll x, ll y) {
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
ll lca(ll x, ll y) {
if (ispr(x, y))
return x;
if (ispr(y, x))
return y;
for (ll i = M - 1; i >= 0; i--) {
if (!ispr(p[x][i], y))
x = p[x][i];
}
x = p[x][0];
return x;
}
ll findMax(ll x, ll y) {
ll ret = 0;
if (x == y)
return 0;
for (ll i = M - 1; i >= 0; i--) {
if (!ispr(p[x][i], y)) {
ret = max(ret, mx[x][i]);
x = p[x][i];
}
}
ret = max(ret, mx[x][0]);
return ret;
}
void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
for (ll i = 0; i < N; i++) {
prt[i] = i;
a[i] = i;
b[i] = i;
fl[i] = 1;
v[i].push_back(i);
}
for (ll i = 0; i < M; i++) {
edges.push_back({W[i], U[i], V[i]});
}
sort(edges.begin(), edges.end(), cmp);
for (auto i : edges) {
merge(i.x, i.y, i.w);
}
for (ll i = 0; i < N; i++) {
// ll pr = findParent(i);
if (!visited[i]) {
dfs(i, i, 0);
}
}
}
ll getMinimumFuelCapacity(ll X, ll Y) {
ll P = lca(X, Y);
if (!ispr(P, X) || !ispr(P, Y) || X == Y)
return -1;
return max(findMax(X, P), findMax(Y, P));
}