#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct edge {
int w, x, y;
};
const int N = 1e5 + 100, M = 23;
vector<pair<int, int>> g[N];
vector<edge> edges;
int prt[N], a[N], b[N], p[N][M], mx[N][M], tin[N], tout[N], tt;
bool fl[N], visited[N];
vector<int> v[N];
bool cmp(edge a, edge b) {
return a.w < b.w;
}
int findParent(int x) {
if (prt[x] == x)
return x;
return prt[x] = findParent(prt[x]);
}
void addEdge(int x, int y, int w) {
g[x].push_back({w, y});
g[y].push_back({w, x});
}
void merge(int x, int y, int w) {
int 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(int x, int par, int w) {
tin[x] = ++tt;
visited[x] = 1;
p[x][0] = par;
mx[x][0] = w;
for (int 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";
}
for (auto to : g[x]) {
if (!visited[to.second])
dfs(to.second, x, to.first);
}
tout[x] = tt;
}
int ispr(int x, int y) {
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int lca(int x, int y) {
if (ispr(x, y))
return x;
if (ispr(y, x))
return y;
for (int i = M - 1; i >= 0; i--) {
if (!ispr(p[x][i], y))
x = p[x][i];
}
x = p[x][0];
return x;
}
int findMax(int x, int y) {
int ret = 0;
if (x == y)
return 0;
for (int 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(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < N; i++) {
prt[i] = i;
a[i] = i;
b[i] = i;
fl[i] = 1;
v[i].push_back(i);
}
for (int 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 (int i = 0; i < N; i++) {
if (!visited[findParent(i)]) {
dfs(i, i, 0);
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int P = lca(X, Y);
if (!ispr(P, X) || !ispr(P, Y) || X == Y)
return -1;
return max(findMax(X, P), findMax(Y, P));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
