제출 #777080

#제출 시각아이디문제언어결과실행 시간메모리
777080LeaRouse경주 (Race) (IOI11_race)C++14
0 / 100
3 ms4948 KiB
#include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); #define ll long long #define ff first using namespace std; const int MAX=2e5+5; vector<pair<int,int>>v[MAX]; int D[MAX],N[MAX],vis[MAX],pa[MAX][25]; void st(int n){ for(int j=1;j<20;j++){ pa[0][j]=0; for(int i=1;i<n;i++){ pa[i][j]=pa[pa[i][j-1]][j-1]; } } } int lca(int x,int y){ if(N[y]>N[x]) swap(x,y); int dif=N[x]-N[y]; for(int i=20;i>=0;i--){ if(dif&(1<<i)){ dif-=(1<<i); x=pa[x][i]; } } if(y==x) return x; for(int i=18;i>=0;i--){ if(pa[x][i]!=pa[y][i]){ x=pa[x][i]; y=pa[y][i]; } } return pa[x][0]; } void dfs(int u){ vis[u]=1; for(auto it:v[u]){ if(vis[it.ff]) continue; D[it.ff]=D[u]+it.second; pa[it.ff][0]=u; N[it.ff]=N[u]+1; dfs(it.ff); } } int best_path(int n,int k,int w[][2],int nc[]){ for(int i=0;i<n;i++){ v[w[i][0]].push_back({w[i][1],nc[i]}); v[w[i][1]].push_back({w[i][0],nc[i]}); } dfs(0); st(n); int b=1e9; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ int a=lca(i,j); if(D[i]+D[j]-2*D[a]==k){ b=min(N[i]+N[j]-2*N[a]+1,b); } } } return b; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...