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 maxn = 1e6 + 10;
int n, m;
vector<int> g[maxn];
vector<pair<int,pair<int,int>>> edges;
int head;
int par[maxn];
int indx[maxn];
int deg[maxn];
bool good[maxn];
int cost[maxn];
int parent(int x) {
if (par[x]==x) return x;
return par[x]=parent(par[x]);
}
const int LOG = 20;
int st[LOG+1][maxn];
int ht[maxn];
void dfs(int at, int p=-1) {
for (int j=1; j<LOG; j++) {
st[j][at]=st[j-1][st[j-1][at]];
}
for (int to: g[at]) {
if (to == p) continue;
st[0][to]=at;
ht[to] = 1+ht[at];
dfs(to, at);
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N;
m=M;
head = n;
for (int i=0; i<M; i++) {
edges.push_back({W[i],{U[i],V[i]}});
}
sort(edges.begin(),edges.end());
for (int i=0; i<n; i++) {
par[i]=i;
indx[i]=i;
deg[i]=0;
good[i]=false;
}
for (auto ed: edges) {
int w = ed.first;
int U = ed.second.first;
int V = ed.second.second;
int u = parent(U);
int v = parent(V);
if (u==v) {
if (!good[indx[u]]) {
g[head].push_back(indx[u]);
good[head]=true;
cost[head]=w;
indx[u] = head++;
}
} else {
deg[u]++;
deg[v]++;
bool ok = (good[indx[u]] || good[indx[v]] || deg[U]>2 || deg[V]>2);
par[v]=u;
g[head].push_back(indx[u]);
g[head].push_back(indx[v]);
good[head] = ok;
cost[head] = w;
indx[u] = head++;
}
}
st[0][head-1] = head-1;
dfs(head-1);
}
int lca(int u, int v) {
if (ht[u]<ht[v]) {
swap(u,v);
}
int dx = ht[u]-ht[v];
for (int j=LOG-1; j>=0; j--) {
if (dx>>j&1) {
u=st[j][u];
}
}
if (u==v) return v;
for (int j=LOG-1; j>=0; j--) {
if (st[j][u]!=st[j][v]) {
u=st[j][u];
v=st[j][v];
}
}
return st[0][v];
}
int getMinimumFuelCapacity(int u, int v) {
if (!good[head-1]) return -1;
int mid = lca(u,v);
if (good[mid]) {
return cost[mid];
}
for (int j=LOG-1; j>=0; j--) {
if (ht[mid] < (1<<j)) continue;
if (!good[st[j][mid]]) {
mid=st[j][mid];
}
}
return cost[st[0][mid]];
}
/*
int main() {
// init(4,4,{0,1,2,3},{1,2,3,0},{1,1,1,1});
// cout<<getMinimumFuelCapacity(1, 2)<<endl;
init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
cout<<getMinimumFuelCapacity(1, 2)<<endl;
cout<<getMinimumFuelCapacity(2, 4)<<endl;
cout<<getMinimumFuelCapacity(0, 1)<<endl;
return 0;
}
*/
# | 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... |