This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
const int Z = 3e5 + 17;
int n, m, q, lg, c[Z], ans[Z];
int r[Z], d[Z], p[20][Z];
tuple <int, int, int> e[Z];
vector <int> adj[Z];
bool ex[Z];
int root (int u)
{
if (u == r[u])
{
return u;
}
return r[u] = root(r[u]);
}
void join (int x, int y, int z)
{
x = root(x);
y = root(y);
++n, r[n] = n;
if (x == y)
{
ex[n] = 1, r[x] = n;
adj[n].push_back(x);
}
else
{
ex[n] = ex[x] | ex[y] | z;
r[x] = r[y] = n;
adj[n].push_back(x);
adj[n].push_back(y);
}
}
int lca (int u, int v)
{
if (d[u] < d[v])
{
swap (u, v);
}
for (int i = lg; i >= 0; --i)
{
if (d[p[i][u]] >= d[v])
{
u = p[i][u];
}
}
if (u == v)
{
return u;
}
for (int i = lg; i >= 0; --i)
{
if (p[i][u] != p[i][v])
{
u = p[i][u], v = p[i][v];
}
}
return p[0][u];
}
void dfs (int u, int pr)
{
d[u] = d[pr] + 1, p[0][u] = pr;
for (int i = 1; i <= lg; ++i)
{
p[i][u] = p[i - 1][p[i - 1][u]];
}
for (int v: adj[u])
{
if (v != pr)
{
dfs (v, u);
}
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
n = N, m = M;
lg = __lg(n + m);
for (int i = 0; i < m; ++i)
{
int u = U[i], v = V[i], w = W[i];
++u, ++v;
e[i] = {w, u, v};
}
for (int i = 1; i <= n; ++i)
{
r[i] = i;
}
sort (e + 1, e + m + 1);
for (int i = 1; i <= m; ++i)
{
auto [w, u, v] = e[i];
++c[u], ++c[v];
int z = (c[u] > 2) | (c[v] > 2);
join (u, v, z);
ans[n] = w;
}
for (int i = n; i >= 0; --i)
{
if (!d[i])
{
dfs (i, 0);
}
}
}
int getMinimumFuelCapacity(int u, int v)
{
++u, ++v;
int z = lca (u, v);
if (ex[z])
{
return ans[z];
}
for (int i = lg; i >= 0; --i)
{
if (p[i][z] && !ex[p[i][z]])
{
z = p[i][z];
}
}
z = p[0][z];
if (!z)
{
return -1;
}
return ans[z];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |