#include "swap.h"
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 123;
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];
pair<int, int> crt[MAXN];
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})};
}
for (auto [u, w] : edg_mst[v]) {
if (u == rt[v].first)
continue;
rt[u] = {v, w};
depth[u] = depth[v] + 1;
}
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, pair<int, int>> lca(int v, int u) {
pair<int, int> ans;
bool swp = 0;
if (depth[u] > depth[v]) {
swap(u, v);
swp = 1;
}
while (depth[v] > depth[u]) {
if (depth[crt[v].first] >= depth[u]) {
ans.first = max(ans.first, crt[v].second);
v = crt[v].first;
} else {
ans.first = max(ans.first, rt[v].second);
v = rt[v].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;
}
}
if (swp)
swap(ans.first, ans.second);
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);
}
int getMinimumFuelCapacity(int X, int Y) {
auto la = lca(X, Y);
return max(la.second.first, la.second.second);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
