Submission #739711

#	Time	Username	Problem	Language	Result	Execution time	Memory
739711		chenyan	Swapping Cities (APIO20_swap)	C++17	0 / 100	405 ms	57100 KiB

swap

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ld long double
#define pii pair<int,int>
#define pdd pair<ld,ld>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define fastio ios::sync_with_stdio(0),cin.tie(0);
#define nl '\n'
#define mN 200010
int dep[mN],n,m,fa[31][mN],dp[31][mN],st[31][mN];
vector<pii>g[mN];
bitset<mN>vis;
void dfs(int v){
	vis[v]=1;
	pii a,b;
	a.ff=b.ff=-1;
	a.ss=b.ss=2e9;
	for(auto[u,w]:g[v]){
		if(vis[u])continue;
		if(a.ff==-1||a.ss>w){
			b=a;
			a.ff=u;
			a.ss=w;
		}
		else if(b.ff==-1||b.ss>w){
			b.ff=u;
			b.ss=w;
		}
	}
	for(auto[u,w]:g[v]){
		if(vis[u])continue;
		dep[u]=dep[v]+1;
		fa[0][u]=v;
		if(a.ff!=u)dp[0][u]=a.ss;
		else dp[0][u]=b.ss;
		st[0][u]=w;
		dfs(u);
	}
}
void init(int NN,int M,vector<int>u,vector<int>v,vector<int>w){
	int i,j;
	n=NN,m=M;
	for(int i=0;i<m;i++){
		g[u[i]].pb({v[i],w[i]});
		g[v[i]].pb({u[i],w[i]});
	}
	fa[0][0]=mN-1;
	for(i=0;i<30;i++)dp[i][0]=2e9,dp[i][mN-1]=2e9;
	for(i=0;i<n;i++)dp[0][i]=2e9;
	for(i=0;i<n;i++)sort(all(g[i]),[](pii a,pii b){return a.ss<b.ss;});
	dfs(0);
	for(i=1;i<30;i++){
		for(j=0;j<n;j++){
			fa[i][j]=fa[i-1][fa[i-1][j]];
			st[i][j]=max(st[i-1][j],st[i-1][fa[i-1][j]]);
			dp[i][j]=min(dp[i-1][j],dp[i-1][fa[i-1][j]]);
		}
	}
}
int getMinimumFuelCapacity(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	int d=dep[u]-dep[v],mi=2e9,i,j,ans=0;
	for(i=0;i<30;i++){
		if(!d)break;
		if((1<<i)&(d-1)){
			ans=max(ans,st[i][u]);
			mi=min(mi,dp[i][u]);
			u=fa[i][u];
		}
	}
	if(d){
		ans=max(ans,st[0][u]);
		if(fa[0][u]!=v)mi=min(mi,dp[0][u]);
		u=fa[0][u];
	}
	if(u==v){
		ans=max(ans,mi);
		return (ans==2e9?-1:ans);
	}
	for(i=29;i>=0;i--){
		while(fa[i][u]!=fa[i][v]){
			ans=max({ans,st[i][u],st[i][v]});
			mi=min({mi,dp[i][u],dp[i][v]});
			u=fa[i][u];
			v=fa[i][v];
		}
	}
	ans=max({ans,st[0][u],st[0][v]});
	for(auto[f,w]:g[fa[0][u]]){
		if(f!=u&&f!=v){
			mi=min(w,mi);
			break;
		}
	}
	ans=max(ans,mi);
	return (ans==2e9?-1:ans);
}
/*
8 7
0 1 1
1 2 5
1 3 2
0 4 3
4 5 6
4 6 4
4 7 5
5
5 7
3 7
2 4
2 3
1 6
signed main(){
	fastio;
}
*/

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:68:31: warning: unused variable 'j' [-Wunused-variable]
   68 |  int d=dep[u]-dep[v],mi=2e9,i,j,ans=0;
      |                               ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27