Submission #1304692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304692		vtnoo	Swapping Cities (APIO20_swap)	C++20	Compilation error	0 ms	0 KiB

swap

#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<pair<int,int>>adj[MAXN];
//~ int dep[MAXN],up[MAXN][LOG],mx[MAXN][LOG],dp[MAXN];
vector<int>dep(MAXN),dp(MAXN,INF);
vector<vector<int>>up(MAXN,vector<int>(LOG)),mx(MAXN,vector<int>(LOG));
vector<vector<pair<int,int>>>adj(MAXN);
void dfs(int u,int p,int d){
	dep[u]=d;
	for(auto[v,c]:adj[u]){
		if(v==p)continue;
		up[v][0]=u;
		mx[v][0]=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;
	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]=up[up[j][i-1]][i-1];
			mx[j][i]=max(mx[j][i-1],mx[up[j][i-1]][i-1]);
		}
	}
	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];
	}
	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 mx[b][dep[b]-dep[a]];
	int ans=0;
	for(int i=LOG-1;i>=0;i--){
		if(up[a][i]!=up[b][i]){
			a=up[a][i];
			b=up[b][i];
			ans=max(ans,mx[a][i]);
			ans=max(ans,mx[b][i]);
		}
	}
	ans=max(ans,mx[a][0]);
	ans=max(ans,mx[b][0]);
	return ans;
}
int getMinimumFuelCapacity(int X, int Y) {
	int pathMax=LCA(X,Y);
	if(dp[X]==INF)return -1;
	return max(pathMax,dp[X]);
}