제출 #152499

#제출 시각아이디문제언어결과실행 시간메모리
152499Kamisama경주 (Race) (IOI11_race)C++14
컴파일 에러
0 ms0 KiB
#include <iostream> #include <cstdio> #include <iomanip> #include <chrono> #include <vector> using namespace std; const int maxn=2e5+7; const int maxk=1e6+7; const int inf=1e9+7; struct Edges{ int x,y,w; }; int n,k,currentLab,res; int subSize[maxn],lab[maxn],d[maxn],lv[maxn],f[maxk]; bool disabled[maxn]; vector<int> adj[maxn],tobeProcessed,depthList; Edges e[maxn]; inline void CalcSize(const int &u){ lab[u]=currentLab; subSize[u]=1; for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(disabled[v] || lab[v]==currentLab) continue; CalcSize(v); subSize[u]+=subSize[v]; } } inline int FindCentroid(int u){ int halfSize=subSize[u]/2; while(true){ int heavyVertex=-1; for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(disabled[v] || subSize[v]>subSize[u]) continue; if(subSize[v]>halfSize){ heavyVertex=v; break; } } if(heavyVertex==-1) break; u=heavyVertex; } return u; } inline void CalcDepth(const int &u){ lab[u]=currentLab; if(d[u]>k) return; depthList.push_back(d[u]); for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(disabled[v] || lab[v]==currentLab) continue; d[v]=d[u]+e[i].w; lv[v]=lv[u]+1; CalcDepth(v); } } inline void Query(const int &u){ if(d[u]>k) return; res=min(res,f[k-d[u]]+lv[u]); for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(disabled[v] || d[v]<=d[u]) continue; Query(v); } } inline void Update(const int &u){ if(d[u]>k) return; f[d[u]]=min(f[d[u]],lv[u]); for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(disabled[v] || d[v]<=d[u]) continue; Update(v); } } inline void ProcessTree(int u){ currentLab++; CalcSize(u); u=FindCentroid(u); for(int x: depthList) f[x]=inf; depthList.resize(0); lv[u]=d[u]=0; currentLab++; CalcDepth(u); for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(disabled[v]) continue; Query(v); Update(v); tobeProcessed.push_back(v); } disabled[u]=true; } inline int best_path(int N, int K, int H[][2], int L[]){ tie(n,k)=tie(N,K); for(int i=0;i<n-1;i++){ e[i]={H[i][0]+1,H[i][1]+1,L[i]}; adj[e[i].x].push_back(i); adj[e[i].y].push_back(i); } fill(f,f+maxk+1,inf); res=inf; tobeProcessed.push_back(1); while(tobeProcessed.size()){ int u=tobeProcessed.back(); tobeProcessed.pop_back(); ProcessTree(u); } return (res==inf)? -1 : res; }

컴파일 시 표준 에러 (stderr) 메시지

/tmp/ccROZvC8.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status