Submission #978171

#TimeUsernameProblemLanguageResultExecution timeMemory
978171irmuunSwapping Cities (APIO20_swap)C++17
0 / 100
2 ms9052 KiB
#include<bits/stdc++.h> #include "swap.h" using namespace std; #define ll long long #define pb push_back #define ff first #define ss second #define all(s) s.begin(),s.end() #define rall(s) s.rbegin(),s.rend() const int N=1e5+5; vector<int>cost(N,2e9); vector<pair<int,int>>adj[N]; int par[N][20],P[N],dep[N],C[N][20]; void calc(int a,int b,int c){ cost[a]=min(cost[a],max(cost[b],c)); cost[b]=min(cost[b],max(cost[a],c)); } void up(int x,int p){//direction P[x]=p; for(auto [y,w]:adj[x]){ if(y!=p){ C[y][0]=w; dep[y]=dep[x]+1; up(y,x); calc(x,y,w); } } } void down(int x,int p){ for(auto [y,w]:adj[x]){ if(y!=p){ calc(x,y,w); down(y,x); } } } int find(int x,int d){ for(int i=19;i>=0;i--){ if(d&(1<<i)){ x=par[x][i]; } } return x; } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); x=find(x,dep[x]-dep[y]); for(int i=19;i>=0;i--){ if(par[x][i]!=par[y][i]){ x=par[x][i]; y=par[y][i]; } } if(x==y) return x; return par[x][0]; } int f(int x,int d){ int res=0; for(int i=19;i>=0;i--){ if(d&(1<<i)){ res=max(res,C[x][i]); x=par[x][i]; } } return res; } void init(int n,int m,vector<int>u,vector<int>v,vector<int>w){ for(int i=0;i<n;i++){ for(int j=0;j<20;j++){ C[i][j]=2e9; } } for(int i=0;i<m;i++){ adj[u[i]].pb({v[i],w[i]}); adj[v[i]].pb({u[i],w[i]}); } for(int i=0;i<n;i++){ if(adj[i].size()>=3){ vector<int>edge; for(auto [j,W]:adj[i]){ edge.pb(W); } sort(all(edge)); cost[i]=edge[2]; } } dep[0]=0; up(0,-1); down(0,-1); for(int i=0;i<n;i++){ par[i][0]=P[i]; } par[0][0]=0; for(int j=1;j<20;j++){ for(int i=0;i<n;i++){ par[i][j]=par[par[i][j-1]][j-1]; C[i][j]=max(C[par[i][j-1]][j-1],C[i][j-1]); } } } int getMinimumFuelCapacity(int x,int y){ int l=lca(x,y); int d=max(f(x,dep[x]-dep[l]),f(y,dep[y]-dep[l])); return max(cost[x],d); }
#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...