| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1304688 | vtnoo | Swapping Cities (APIO20_swap) | C++20 | 0 ms | 0 KiB |
#include "swap.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=1e5,LOG=18,INF=1e9+7;
int n,m;
vector<basic_string<pair<int,int>>>adj;
pair<int,int>up[MAXN][LOG];
vector<int>dep,dp;
void dfs(int u,int p,int d){
dep[u]=d;
for(auto[v,c]:adj[u]){
if(v==p)continue;
up[v][0].fst=u;
up[v][0].snd=c;
dfs(v,u,d+1);
}
}
void dfs2(int u,int p){
for(auto[v,c]:adj[u]){
if(v==p)continue;
dfs2(v,u);
dp[u]=min(dp[u],max(dp[v],c));
}
}
void dfs3(int u,int p){
for(auto[v,c]:adj[u]){
if(v==p)continue;
dp[u]=min(dp[u],max(dp[v],c));
dfs3(v,u);
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N,m=M;
dep.resize(n);
dp.resize(n);
adj.resize(n);
fore(i,0,m){
adj[U[i]].pb({V[i],W[i]});
adj[V[i]].pb({U[i],W[i]});
}
dfs(0,0,0);
fore(i,1,LOG){
fore(j,0,n){
up[j][i].fst=up[up[j][i-1].fst][i-1].fst;
up[j][i].snd=max(up[j][i-1].snd,up[up[j][i-1].fst][i-1].snd);
}
}
fore(i,0,n){
int best1=INF,best2=INF,best3=INF;
for(auto[v,c]:adj[i]){
if(c<best1){
best3=best2;
best2=best1;
best1=c;
}else if(c<best2){
best3=best2;
best2=c;
}else if(c<best3){
best3=c;
}
}
dp[i]=best3;
}
dfs2(0,0);
dfs3(0,0);
}
int jump(int a, int d){
fore(i,0,LOG){
if(d&(1<<i))a=up[a][i].fst;
}
return a;
}
int LCA(int a,int b){
if(dep[a]>dep[b])swap(a,b);
b=jump(b,dep[b]-dep[a]);
if(a==b)return up[b][dep[b]-dep[a]].snd;
int ans=0;
for(int i=LOG-1;i>=0;i--){
if(up[a][i].fst!=up[b][i].fst){
a=up[a][i].fst;
b=up[b][i].fst;
ans=max(ans,up[a][i].snd);
ans=max(ans,up[b][i].snd);
}
}
ans=max(ans,up[a][0].snd);
ans=max(ans,up[b][0].snd);
return ans;
}
int getMinimumFuelCapacity(int X, int Y) {
int pathMax=LCA(X,Y);
if(dp[X]==INF)return -1;
return max(pathMax,dp[X]);
}