//#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N =2e5 + 9 , mod = 1e9 + 7;
ll p[N], sz[N] , a[N] , b[N] , dp[N] , c[N][25] , d[N] , par[N][25] , mx[N][25] , us[N] , us1[N];
vector<pair<ll,ll>>v[N] , v1[N];
int get(int x){
return (p[x] == x ? x : get(p[x]));
}
void join(int X , int Y , ll k){
int x = get(X) , y = get(Y);
if(x != y){
if(sz[x] < sz[y])
swap(x , y);
p[y] = x;
sz[x] += sz[y];
v[min(X , Y)].pb({k , max(X , Y)});
}else {
v1[X].pb({k , Y});
v1[Y].pb({k , X});
}
}
ll timer = 0;
void dfs(int n , int p = 0 , ll k = 0){
a[n] = k;
if(n == 1)
a[n] = 1e18;
par[n][0] = p;
if(v[p].size())
c[n][0] = v[p][0].fi;
else
c[n][0] = 1e18;
if(v[p].size() && v[p][0].se == n){
if(v[p].size() > 1)
c[n][0] = v[p][1].fi;
else
c[n][0] = 1e18;
}
mx[n][0] = k;
us[n] = ++timer;
for(int i = 1; i <= 20; i++){
par[n][i] = par[par[n][i - 1]][i - 1] ;
mx[n][i] = max(mx[n][i - 1] , mx[par[n][i - 1]][i - 1]);
c[n][i] = min(c[n][i - 1] , c[par[n][i - 1]][i - 1]);
}
for(auto to : v[n])
dfs(to.se , n , to.fi);
if(v1[n].size())
dp[n] = min(dp[n] , v1[n][0].fi);
if(v[n].size() > 1)
dp[n] = min(dp[n] , v[n][1].fi);
dp[p] = min(dp[p] , max(k , dp[n]));
us1[n] = ++timer;
}
bool ok(int u, int v)
{
return (u && us[u] <= us[v] && us1[u] >= us1[v]);
}
ll get(int x , int y){
ll mn = 1e18 , ans = 0;
for(int i = 20; i >= 0; i--){
if(!ok(par[y][i] , x)){
mn = min(mn , c[y][i]);
ans = max(ans , mx[y][i]);
y = par[y][i];
}
}
ans = max(ans , mx[y][0]);
mn = min({mn , dp[y]});
ans = max(ans , mn);
if(ans == 1e18)
ans = -1;
return ans;
}
ll lca(int x , int y){
if(ok(x , y)){
return get(x , y);
}
if(ok(y , x))
return get(y , x);
ll mn = 1e18 , ans = 0;
mn = min({mn , dp[x] , dp[y]});
for(int i = 20; i >= 0; i--){
if(!ok(par[y][i] , x)){
mn = min(mn , c[y][i]);
ans = max(ans , mx[y][i]);
y = par[y][i];
}
}
for(int i = 20; i >= 0; i--){
if(!ok(par[x][i] , y)){
mn = min(mn , c[x][i]);
ans = max(ans , mx[x][i]);
x = par[x][i];
}
}
mn = min(mn, a[par[x][0]]);
for(int i = 0; i < 3 && i < v[par[x][0]].size(); i++)
if(v[par[x][0]][i].se != x && v[par[x][0]][i].se != y)
mn = min(mn ,1ll * v[par[x][0]][i].fi);
ans = max(ans , mn);
if(ans == 1e18)
ans = -1;
return ans;
}
void init(int n , int m , vector<int>v , vector<int>u , vector<int>c)
{
vector<pair<ll,pair<ll,ll>>>vc;
for(int i = 0; i <= n; i++)
dp[i] = 1e18 , p[i] = i , sz[i] = 1;
for(int i = 0; i < m; i++)
vc.pb({c[i] , {v[i] + 1, u[i] + 1}});
sort(all(vc));
for(auto to : vc)
join(to.se.fi , to.se.se , to.fi);
for(int i = 1; i <= n ; i++)
sort(all(::v[i])) , sort(rall(::v1[i]));
dfs(1);
}
ll getMinimumFuelCapacity(int l, int r) {
l++ , r++;
return lca(l , r);
}
int main(){
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)<<"\n";
cout<<getMinimumFuelCapacity(2,4)<<"\n";
cout<<getMinimumFuelCapacity(0,1)<<"\n";
}
Compilation message
swap.cpp: In function 'long long int lca(int, int)':
swap.cpp:121:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i = 0; i < 3 && i < v[par[x][0]].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccjXkr3Q.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccioIL4S.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
