#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
using ll = long long;
const int INF = 1e9 + 7;
vector<int> dpth;
vector<vector<pair<int, int>>> adj;
vector<array<int, 20>> up, ans, res;
void DFS(int k, int p, int x);
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
adj.resize(N);
dpth.resize(N);
up = ans = res = vector<array<int, 20>>(N);
for (int i = 0; i < M; i++)
{
adj[U[i]].emplace_back(V[i], W[i]);
adj[V[i]].emplace_back(U[i], W[i]);
}
res[0][0] = INF;
DFS(0, 0, INF);
}
void DFS(int k, int p, int x)
{
dpth[k] = dpth[p] + 1;
up[k][0] = p;
ans[k][0] = x;
for (int i = 1; i < 20; i++)
{
up[k][i] = up[up[k][i - 1]][i - 1];
ans[k][i] = min(ans[k][i - 1], ans[up[k][i - 1]][i - 1]);
res[k][i] = max(res[k][i - 1], res[up[k][i - 1]][i - 1]);
}
int mn = INF, mn2 = INF;
for (pair<int, int> i : adj[k])
if (i.F == p)
continue;
else if (i.S < mn)
{
mn2 = mn;
mn = i.S;
}
else if (i.S < mn2)
mn2 = i.S;
for (pair<int, int> i : adj[k])
{
if (i.F == p)
continue;
res[i.F][0] = i.S;
if (i.S == mn)
DFS(i.F, k, mn2);
else
DFS(i.F, k, mn);
}
}
array<int, 3> kth_ancestor(int a, int x)
{
int as = INF, rs = -INF;
for (int i = 0; i < 20; i++)
{
if (x & (1 << i))
{
as = min(as, ans[a][i]);
rs = max(rs, res[a][i]);
a = up[a][i];
}
}
return {a, as, rs};
}
int getMinimumFuelCapacity(int X, int Y)
{
if (dpth[X] < dpth[Y])
swap(X, Y);
int X0 = X, Y0 = Y;
array<int, 3> ret = kth_ancestor(X, dpth[X] - dpth[Y]);
if (ret[0] == Y)
return (ret[2] == INF ? -1 : max(ret[1], ret[2]));
X = ret[0];
for (int i = 19; i >= 0; i--)
if (up[X][i] != up[Y][i])
X = up[X][i], Y = up[Y][i];
array<int, 3> rs1 = kth_ancestor(X0, dpth[X0] - dpth[X]);
array<int, 3> rs2 = kth_ancestor(Y0, dpth[Y0] - dpth[Y]);
int mn = INF, x = -INF, y = -INF;
for (pair<int, int> i : adj[up[X][0]])
{
if (i.F == X)
{
x = i.S;
continue;
}
if (i.F == Y)
{
y = i.S;
continue;
}
if (i.F == up[up[X][0]][0])
continue;
mn = min(mn, i.S);
}
rs1[1] = min(rs1[1], mn);
rs1[2] = max(rs1[2], x);
rs2[2] = max(rs2[2], y);
return (rs1[1] != INF || rs2[1] != INF ? max(max(rs1[2], rs2[2]), min(rs1[1], rs2[1])) : -1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
