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 "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 5;
const int Nmax = 1e5 + 5;
int rang[Nmax], t[Nmax], A[Nmax], B[Nmax], up[Nmax], good[Nmax], level[Nmax];
bool chain[Nmax];
int n, m;
vector<int> v[Nmax];
int boss(int x)
{
if(x == t[x]) return x;
return boss(t[x]);
}
bool endpoints(int x, int y, int a, int b)
{
//assert(boss(a) == x && boss(b) == y);
assert(chain[x] && chain[y]);
return (A[x] == a || B[x] == a) && (A[y] == b || B[y] == b);
}
void combine_chains(int x, int y, int a, int b)
{
B[y] = (A[y] == b ? B[y] : A[y]);
A[y] = (A[x] == a ? B[x] : A[x]);
}
void dfs(int node)
{
for(auto it : v[node])
{
good[it] = min(good[it], max(good[node], up[it]));
level[it] = level[node] + 1;
dfs(it);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
n = N; m = M;
vector<int> ord(m);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&] (int x, int y) { return W[x] < W[y]; } );
for(int j = 0; j<n; ++j)
{
good[j] = inf;
chain[j] = 1;
A[j] = B[j] = j;
rang[j] = 0;
t[j] = j;
}
for(auto i : ord)
{
int x = U[i], y = V[i], cost = W[i];
x = boss(x);
y = boss(y);
if(x == y)
{
good[x] = min(good[x], cost);
chain[x] = 0;
continue;
}
if(rang[x] > rang[y])
{
swap(x, y);
swap(U[i], V[i]);
}
if(rang[x] == rang[y]) ++rang[y];
t[x] = y;
v[y].push_back(x);
up[x] = cost;
if(chain[y])
{
if(!chain[x] || (chain[x] && !endpoints(x, y, U[i], V[i])))
chain[y] = 0, good[y] = min(good[y], cost);
else
combine_chains(x, y, U[i], V[i]);
}
}
dfs(boss(0));
}
int getMinimumFuelCapacity(int x, int y)
{
int ans = 0;
while(x != y)
{
if(level[x] > level[y]) ans = max(ans, up[x]), x = t[x];
else ans = max(ans, up[y]), y = t[y];
}
ans = max(ans, good[x]);
if(ans == inf) return -1;
return ans;
}
# | 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... |