Submission #739711

#TimeUsernameProblemLanguageResultExecution timeMemory
739711chenyanSwapping Cities (APIO20_swap)C++17
0 / 100
405 ms57100 KiB
#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;
      |                               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...