#include <bits/stdc++.h>
//#include "swap.h"
#include "grader.cpp"
using namespace std ;
const int inf = 2e9 ;
const int MAX = 1e5 + 10 ;
int par[MAX] , sz[MAX] , cyc[MAX] ;
vector<int>comp[MAX] ;
int n , m ;
void Init()
{
for(int i = 1 ; i <= n ; ++i)
cyc[i] = inf , comp[i].push_back(i) , par[i] = i , sz[i] = 1 ;
}
int root(int node)
{
if(par[node] == node)
return node ;
return (par[node] = root(par[node])) ;
}
void Union(int x , int y , int z)
{
int a = root(x) ;
int b = root(y) ;
if(cyc[a] == inf && cyc[b] != inf)
{
for(auto &node : comp[a])
cyc[node] = z ;
}
else if(cyc[a] != inf && cyc[b] == inf)
{
for(auto &node : comp[b])
cyc[node] = z ;
}
if(sz[a] < sz[b])
swap(a , b) ;
while(comp[b].size())
comp[a].push_back(comp[b].back()) , comp[b].pop_back() ;
par[b] = a ;
sz[a] += sz[b] ;
}
vector< vector< pair<int , int> > >adj(MAX) ;
int arr[MAX] ;
int P[MAX][20] , Max[MAX][20] , val[MAX][20] , dep[MAX] ;
void dfs(int node , int par , int x , int y)
{
P[node][0] = par ;
Max[node][0] = x ;
val[node][0] = y ;
for(int i = 1 ; i < 17 ; ++i)
{
P[node][i] = P[P[node][i-1]][i-1] ;
Max[node][i] = max(Max[node][i-1] , Max[P[node][i-1]][i-1]) ;
val[node][i] = min(val[node][i-1] , val[P[node][i-1]][i-1]) ;
}
vector<int>v ;
for(auto &child : adj[node])
{
if(child.first == par)
continue ;
v.push_back(child.second) ;
}
sort(v.begin() , v.end()) ;
int b = inf ;
if(v.size() > 1)
b = v[1] ;
arr[node] = x ;
if(v.size() > 2)
arr[node] = min(arr[node] , v[2]) ;
for(auto &child : adj[node])
{
if(child.first == par)
continue ;
dep[child.first] = dep[node] + 1 ;
dfs(child.first , node , child.second , b) ;
}
}
int calc(int x , int y)
{
if(dep[x] < dep[y])
swap(x , y) ;
int a = -inf , b = inf ;
b = min(cyc[x] , cyc[y]) ;
for(int i = 16 ; i >= 0 ; --i)
{
if((dep[x] - (1 << i)) > dep[y])
{
a = max(a , Max[x][i]) ;
b = min(b , val[x][i]) ;
x = P[x][i] ;
}
}
if(dep[x] != dep[y])
{
if(P[x][0] != y)
b = min(b , val[x][0]) ;
a = max(a , Max[x][0]) ;
x = P[x][0] ;
}
if(x == y)
return max(a , b) ;
for(int i = 16 ; i >= 0 ; --i)
{
if(P[x][i] != P[y][i])
{
a = max(a , max(Max[x][i] , Max[y][i])) ;
b = min(b , min(val[x][i] , val[y][i])) ;
x = P[x][i] , y = P[y][i] ;
}
}
a = max(a , max(Max[x][0] , Max[y][0])) ;
b = min(b , arr[P[x][0]]) ;
return max(a , b) ;
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N , m = M ;
vector< array<int , 3> >v ;
for(int i = 0 ; i < m ; ++i)
v.push_back({W[i] , U[i]+1 , V[i]+1}) ;
Init() ;
sort(v.begin() , v.end()) ;
for(auto &a : v)
{
int x = a[1] , y = a[2] , z = a[0] ;
if(root(x) == root(y))
{
int r = root(x) ;
if(cyc[r] == inf)
{
for(auto &node : comp[r])
cyc[node] = z ;
}
}
else
Union(x , y , z) , adj[x].emplace_back(y , z) , adj[y].emplace_back(x , z) ;
}
dfs(1 , 0 , inf , inf) ;
}
int getMinimumFuelCapacity(int x, int y)
{
x++ , y++ ;
int ans = calc(x , y) ;
if(ans == inf)
ans = -1 ;
return ans ;
}
Compilation message
/usr/bin/ld: /tmp/cchnKlUN.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccP4rVFO.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
