| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 349529 | parsabahrami | 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 "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
typedef long long int ll;
typedef pair<int, int > pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 2e5 + 10;
int P[19][N], H[N], C[N], rt[N], D[N], M[N], tim;
int Find(int v) {
return !rt[v] ? v : rt[v] = Find(rt[v]);
}
void Union(int u, int v, int w) {
u = Find(u), v = Find(v);
if (u == v) {
++tim;
P[0][u] = rt[u] = P[0][tim] = tim;
C[u] = w; M[tim] = 1;
} else {
++tim;
rt[u] = rt[v] = P[0][u] = P[0][v] = P[0][tim] = tim;
C[u] = C[v] = w;
M[tim] = M[u] | M[v];
}
}
void init(int n, int m, int U[], int V[], int W[]) {
tim = n - 1; vector<pair<int, pii>> E;
for (int i = 0; i < m; i++) {
E.push_back({W[i], {U[i], V[i]}});
}
sort(E.begin(), E.end());
for (auto e : E) {
int w = e.F, u = e.S.F, v = e.S.S;
D[u]++, D[v]++;
Union(u, v, w);
if (D[u] > 2 || D[v] > 2) M[Find(u)] = 1;
}
for (int i = 1; i < 19; i++) for (int j = 0; j <= tim; j++) P[i][j] = P[i - 1][P[i - 1][j]];
for (int i = tim - 1; i >= 0; i--) H[i] = H[P[0][i]] + 1;
}
int getMinimumFuelCapacity(int u, int v) {
if (H[u] < H[v]) swap(u, v);
for (int i = H[u] - H[v]; i; i -= i & -i) u = P[__builtin_ctz(i)][u];
for (int i = 18; ~i; i--) {
if (P[i][u] != P[i][v] || !M[P[i][v]]) {
u = P[i][u], v = P[i][v];
}
}
if (P[0][u] != P[0][v]) return -1;
if (!M[P[0][u]]) return -1;
return C[u];
}