#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] , dp1[N] , c[N][25] , d[N] , par[N][25] , mx[N][25] , us[N] , us1[N];
vector<pair<ll,ll>>v[N] , v1[N] , vc[N] , vv[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];
vv[X].pb({k , Y});
vv[Y].pb({k , X});
}else {
v1[X].pb({k , Y});
v1[Y].pb({k , X});
}
}
ll timer = 0;
void dd(int n ,int p = 0 , int k = 0){
if(p)
v[p].pb({k , n});
for(auto to : vv[n])
if(to.se != p)
dd(to.se , n , to.fi);
}
void dfs(int n , int p = 0 , ll k = 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;
}
if(v1[p].size())
c[n][0] = min(c[n][0] , v1[p][0].fi);
if(v1[n].size())
c[n][0] = min(c[n][0] , v1[n][0].fi);
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;
}
void dfs1(int n , int p = 0 , ll k = 1e18 , ll ans = 1e18){
if(v1[n].size())
ans = min(ans , v1[n][0].fi);
dp1[n] = ans;
v[n].pb({k , p});
for(auto to : v[n])
if(to.se != p)
vc[n].pb({max(to.fi , dp[to.se]) , to.se});
sort(all(v[n]));
sort(all(vc[n]));
for(auto to : v[n]){
if(to.se != p){
ll ans1 = ans;
if(v[n].size() >= 3){
if(v[n][1].se == to.se || v[n][0].se == to.se)
ans1 = min(ans1, v[n][2].fi);
else
ans1 = min(ans1 , v[n][1].fi);
}
if(vc[n][0].se != to.se)
ans1 = min(ans1 ,vc[n][0].fi);
else if(vc[n].size() > 1)
ans1 = min(ans1 , vc[n][1].fi);
dfs1(to.se , n , to.fi , max(ans1 , to.fi));
}
}
}
bool ok(int u, int v)
{
return (u == 0 || (us[u] <= us[v] && us1[u] >= us1[v]));
}
ll get(int x , int y){
ll mn = 1e18 , ans = 0;
mn = min({mn , dp[y]});
for(int i = 18; 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 , dp1[y]});
ans = max(ans , mn);
y = p[y][0];
if(v1[y].size())
mn = min(mn , v1[y][0].fi);
if(ans > 1e9)
ans = -1;
return ans;
}
ll mm = 0;
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 = 18; 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 = 18; 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];
}
}
ans = max(ans , mx[x][0]);
ans = max(ans , mx[y][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 ,v[par[x][0]][i].fi);
x = par[x][0];
if(v1[x].size())
mn = min(mn , v1[x][0].fi);
ans = max(ans , mn);
if(ans > 1e9)
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);
dd(1);
for(int i = 1; i <= n ; i++)
sort(all(::v[i])) , sort(rall(::v1[i]));
dfs(1);
dfs1(1);
}
int getMinimumFuelCapacity(int l, int r) {
l++ , r++;
return lca(l , r);
}
/*
int main(){
init(4, 4, {0, 0, 1 , 2}, {1 , 3 , 2 , 3}, {1 , 3 , 2 , 4});
cout<<getMinimumFuelCapacity(0,1)<<"\n";
cout<<getMinimumFuelCapacity(0,2)<<"\n";
cout<<getMinimumFuelCapacity(0,3)<<"\n";
cout<<getMinimumFuelCapacity(1,2)<<"\n";
cout<<getMinimumFuelCapacity(1,3)<<"\n";
cout<<getMinimumFuelCapacity(2,3)<<"\n";
}*/
Compilation message
swap.cpp: In function 'long long int get(int, int)':
swap.cpp:131:13: error: invalid types 'long long int[int]' for array subscript
131 | y = p[y][0];
| ^
swap.cpp: In function 'long long int lca(int, int)':
swap.cpp:164: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]
164 | for(int i = 0; i < 3 && i < v[par[x][0]].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~
