# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
758424 | yellowtoad | Swapping Cities (APIO20_swap) | C++17 | 453 ms | 87244 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 <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
#define int long long
using namespace std;
int n, m, freq[100010], p[100010], id[100010], par[300010][20], depth[300010];
bool can[300010];
pair<int,pair<int,int>> ed[200010];
vector<int> edge[300010];
int dsu(int u) {
if (p[u] == u) return u;
return (p[u] = dsu(p[u]));
}
void dfs(int u, int d) {
int v = par[u][0];
depth[u] = d;
for (int i = 1; i <= 19; i++) {
if (v == -1) {
par[u][i] = -1;
continue;
}
par[u][i] = par[v][i-1];
v = par[u][i];
}
for (int i = 0; i < edge[u].size(); i++) dfs(edge[u][i],d+1);
}
int lca(int u, int v) {
if (depth[v] < depth[u]) swap(u,v);
int i = 19;
while (depth[v] != depth[u]) {
if ((par[v][i] != -1) && (depth[par[v][i]] >= depth[u])) v = par[v][i];
i--;
}
if (v == u) return u;
i = 19;
while (i >= 0) {
if (par[v][i] != par[u][i]) {
u = par[u][i];
v = par[v][i];
}
i--;
}
return par[u][0];
}
void init(signed N, signed M, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
n = N; m = M;
for (int i = 0; i < m; i++) ed[i] = {W[i],{U[i],V[i]}};
sort(ed,ed+m);
for (int i = 0; i < n; i++) p[i] = id[i] = i;
for (int i = 0; i < m; i++) {
int u = ed[i].s.f, v = ed[i].s.s, w = ed[i].f;
if (dsu(u) == dsu(v)) {
par[id[dsu(u)]][0] = n+i;
edge[n+i].push_back(id[dsu(u)]);
id[dsu(u)] = n+i;
freq[u]++;
freq[v]++;
can[n+i] = 1;
} else {
par[id[dsu(u)]][0] = n+i;
par[id[dsu(v)]][0] = n+i;
edge[n+i].push_back(id[dsu(u)]);
edge[n+i].push_back(id[dsu(v)]);
freq[u]++;
freq[v]++;
if ((freq[u] >= 3) || (freq[v] >= 3) || (can[id[dsu(u)]]) || (can[id[dsu(v)]])) can[n+i] = 1;
p[dsu(v)] = p[dsu(u)];
id[dsu(u)] = n+i;
}
}
for (int i = 0; i <= 19; i++) par[n+m-1][i] = -1;
dfs(n+m-1,1);
/*for (int i = 0; i < n+m; i++) {
for (int j = 0; j <= 19; j++) cout << par[i][j] << " ";
cout << endl;
}*/
}
signed getMinimumFuelCapacity(signed U, signed V) {
int u = lca(U,V);
if (can[u]) return ed[u-n].f;
int i = 19;
while (i >= 0) {
if ((par[u][i] != -1) && (!can[par[u][i]])) u = par[u][i];
i--;
}
if (par[u][0] == -1) return -1;
return ed[par[u][0]-n].f;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |