#include "swap.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 123;
const int INF = 1e9 + 177013;
vector<pair<int, int>> edg[MAXN];
vector<pair<int, int>> edg_mst[MAXN];
int depth[MAXN];
int timer = 0;
int tin[MAXN];
int tout[MAXN];
pair<int, int> rt[MAXN];
int rt_deviate[MAXN];
pair<int, int> crt[MAXN];
int crt_deviate[MAXN];
pair<int, int> min_deviation(int v, vector<int> vc) {
for (auto [u, w] : edg_mst[v]) {
bool isok = true;
for (auto t : vc) {
if (t == u) {
isok = false;
break;
}
}
if (isok)
return {u, w};
}
return {-1, INF};
}
void dfs(int v) {
tin[v] = timer++;
int rtv = rt[v].first;
int crtrtv = crt[rtv].first;
int crtcrtrtv = crt[crtrtv].first;
if (depth[rtv] - depth[crtrtv] == depth[crtrtv] - depth[crtcrtrtv]) {
crt[v] = {crtcrtrtv, max({rt[v].second, crt[rtv].second, crt[crtrtv].second})};
crt_deviate[v] = min({rt_deviate[v], crt_deviate[rtv], crt_deviate[crtrtv]});
} else {
crt[v] = rt[v];
}
for (auto [u, w] : edg_mst[v]) {
if (u == rt[v].first)
continue;
rt[u] = {v, w};
rt_deviate[u] = min_deviation(v, vector<int>{u, rt[v].first}).second;
depth[u] = depth[v] + 1;
dfs(u);
}
tout[v] = timer;
}
struct dsu {
void resize(int n) {
par.resize(n);
sz.assign(n, 1);
for (int i = 0; i < n; ++i)
par[i] = i;
}
int gst(int i) {
if (par[i] == i)
return i;
return par[i] = gst(par[i]);
}
bool unite(int i, int j) {
i = gst(i);
j = gst(j);
if (i == j)
return false;
if (sz[i] < sz[j])
swap(i, j);
par[j] = i;
sz[i] += sz[j];
return true;
}
private:
vector<int> par;
vector<int> sz;
};
pair<int, int> get_up(int v, int d) {
int ans = 0;
while (depth[v] > d) {
if (depth[crt[v].first] >= d) {
ans = max(ans, crt[v].second);
v = crt[v].first;
} else {
ans = max(ans, rt[v].second);
v = rt[v].first;
}
}
return {v, ans};
}
pair<int, pair<int, int>> lca(int v, int u) {
pair<int, int> ans(0, 0);
if (depth[u] > depth[v]) {
pair<int, int> p = get_up(u, depth[v]);
ans.second = p.second;
u = p.first;
}
if (depth[u] < depth[v]) {
pair<int, int> p = get_up(v, depth[u]);
ans.first = p.second;
v = p.first;
}
while (v != u) {
if (crt[v].first == crt[u].first) {
ans.first = max(ans.first, rt[v].second);
v = rt[v].first;
ans.second = max(ans.second, rt[u].second);
u = rt[u].first;
} else {
ans.first = max(ans.first, crt[v].second);
v = crt[v].first;
ans.second = max(ans.second, crt[u].second);
u = crt[u].first;
}
}
return {v, ans};
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
vector<pair<int, pair<int, int>>> edg_weight(m);
for (int i = 0; i < m; ++i) {
edg_weight[i] = {W[i], {U[i], V[i]}};
}
sort(edg_weight.begin(), edg_weight.end());
dsu su;
su.resize(n);
for (auto [w, e] : edg_weight) {
auto [u, v] = e;
if (su.unite(u, v)) {
edg_mst[u].push_back({v, w});
edg_mst[v].push_back({u, w});
}
}
dfs(0);
}
pair<int, int> get_up_deviate(int v, int d) {
int ans = INF;
while (depth[v] > d) {
if (depth[crt[v].first] >= d) {
ans = min(ans, crt_deviate[v]);
v = crt[v].first;
} else{
ans = max(ans, rt_deviate[v]);
v = rt[v].first;
}
}
return {v, ans};
}
int second_deviation(int v, int u) {
int w = min_deviation(v, vector<int>{u}).first;
return min_deviation(v, vector<int>{u, w}).second;
}
int getMinimumFuelCapacity(int X, int Y) {
auto [a, p] = lca(X, Y);
int ans = max(p.first, p.second);
int ans0 = INF;
auto [u, wu] = get_up_deviate(X, depth[a] + 1);
auto [v, wv] = get_up_deviate(Y, depth[a] + 1);
ans0 = min(wu, wv);
int x0 = rt[X].first;
int y0 = rt[Y].first;
if (X != a && Y != a) {
ans0 = min(ans0, min_deviation(a, vector<int>{u, v}).second);
} else if (X == a) {
x0 = v;
} else {
y0 = u;
}
ans0 = min(ans0, second_deviation(X, x0));
ans0 = min(ans0, second_deviation(Y, y0));
if (ans0 == INF)
return -1;
return max(ans, ans0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
186 ms |
17620 KB |
Output is correct |
| 4 |
Correct |
213 ms |
18112 KB |
Output is correct |
| 5 |
Correct |
200 ms |
17824 KB |
Output is correct |
| 6 |
Correct |
199 ms |
18112 KB |
Output is correct |
| 7 |
Correct |
168 ms |
17932 KB |
Output is correct |
| 8 |
Correct |
193 ms |
17496 KB |
Output is correct |
| 9 |
Correct |
212 ms |
18000 KB |
Output is correct |
| 10 |
Correct |
170 ms |
17332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
