#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = (int) 1e9 + 7;
vector<int> edge_ids;
vector<int> papa_dsu;
vector<int> wait_outside;
vector<int> par;
vector<int> dep;
vector<int> weight_up;
vector<int> oth_min;
vector<vector<pair<int, int>>> g;
bool deja = 0;
int get_root(int a) {
if (papa_dsu[a] == a) {
return a;
} else {
return papa_dsu[a] = get_root(papa_dsu[a]);
}
}
void dfs(int a, int p = -1) {
par[a] = p;
vector<pair<int, int>> kids;
for (auto &it : g[a]) {
int b = it.first;
if (b == p) {
continue;
}
weight_up[b] = it.second;
dep[b] = 1 + dep[a];
dfs(b, a);
kids.push_back(it);
}
g[a] = kids;
int mn = INF;
for (int rev = 0; rev < 2; rev++) {
for (auto &it : g[a]) {
int b = it.first;
oth_min[b] = min(oth_min[b], mn);
mn = min(mn, weight_up[b]);
}
reverse(g[a].begin(), g[a].end());
}
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
par.resize(n, -1);
dep.resize(n, 0);
weight_up.resize(n, INF);
oth_min.resize(n, INF);
assert(deja == 0);
deja = 1;
assert((int) U.size() == m);
assert((int) V.size() == m);
assert((int) W.size() == m);
g.resize(n);
edge_ids.resize(m);
iota(edge_ids.begin(), edge_ids.end(), 0);
sort(edge_ids.begin(), edge_ids.end(), [&] (int i, int j) {
return W[i] < W[j];
});
papa_dsu.resize(n);
iota(papa_dsu.begin(), papa_dsu.end(), 0);
wait_outside.resize(n, INF);
for (int j = 0; j < m; j++) {
int index = edge_ids[j];
int a = U[index];
int b = V[index];
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (get_root(a) != get_root(b)) {
g[a].push_back({b, W[index]});
g[b].push_back({a, W[index]});
papa_dsu[get_root(a)] = get_root(b);
} else {
wait_outside[a] = min(wait_outside[a], W[index]);
wait_outside[b] = min(wait_outside[b], W[index]);
}
}
dfs(0);
}
int lca_dumb(int x, int y) {
while (x != y) {
if (dep[x] > dep[y]) {
swap(x, y);
}
// dep[x] <= dep[y];
y = par[y];
}
return x;
}
int iq = 0;
int getMinimumFuelCapacity(int x, int y) {
iq++;
if (x == y) {
return 0;
}
int z = lca_dumb(x, y);
bool init_good = (x != z && y != z);
int ix = x;
int iy = y;
int sol = 0, sol2 = INF;
sol2 = min(sol2, wait_outside[x]);
sol2 = min(sol2, wait_outside[y]);
// cout << par[x] << " " << par[y] << "\n";
while (x != y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
//cout << " = " << x << " " << y << "\n";
assert(dep[x] >= dep[y]);
// cobor x
if (par[x] != x) {
sol = max(sol, weight_up[x]);
}
if (par[x] != z) {
sol2 = min(sol2, oth_min[x]);
}
x = par[x];
sol2 = min(sol2, wait_outside[x]);
}
if (init_good) {
sol2 = min(sol2, weight_up[z]);
while (par[ix] != z) {
ix = par[ix];
}
while (par[iy] != z) {
iy = par[iy];
}
for (auto &it : g[z]) {
int b = it.first;
if (b == ix || b == iy) {
continue;
}
sol2 = min(sol2, weight_up[b]);
}
}
if (sol2 == INF) {
return -1;
}
return max(sol, sol2);
//cout << " = " << ix << " " << iy << "\n";
cout << sol << "\n";
cout << sol2 << "\n";
exit(0);
return max(sol, sol2);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
2066 ms |
14100 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
