이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> v[200001], c[200001], chk1, chk2;
bool visited[200001];
int sz[200001], ans = 1000000000, n, k;
int mindep[1000001], newdep[1000001];
int getSize(int x, int y){
sz[x] = 1;
for(int i = 0;i < v[x].size();i++){
if(v[x][i] != y && !visited[v[x][i]]) sz[x] += getSize(v[x][i], x);
}
return sz[x];
}
int getCentroid(int x, int y, int z){
for(int i = 0;i < v[x].size();i++){
if(v[x][i] != y && sz[v[x][i]]*2 > z && !visited[v[x][i]]) return getCentroid(v[x][i], x, z);
}
return x;
}
void dfs(int x, int y, int dep, int cnt){
if(dep == k) ans = min(ans, cnt);
if(dep > k) return;
if(mindep[k-dep] != 1e9) ans = min(ans, cnt + mindep[k-dep]);
newdep[dep] = min(newdep[dep], cnt);
chk1.push_back(dep);
chk2.push_back(dep);
for(int i = 0;i < v[x].size();i++){
if(v[x][i] != y && !visited[v[x][i]]) dfs(v[x][i], x, dep+c[x][i], cnt+1);
}
}
void dnc(int x){
int cent = getCentroid(x, -1, getSize(x, -1));
for(int i = 0;i < v[cent].size();i++){
if(!visited[v[cent][i]]){
dfs(v[cent][i], cent, c[cent][i], 1);
for(int j = 0;j < chk1.size();j++) mindep[chk1[j]] = min(mindep[chk1[j]], newdep[chk1[j]]);
chk1.clear();
}
}
for(int j = 0;j < chk2.size();j++) mindep[chk2[j]] = newdep[chk2[j]] = 1e9;
chk2.clear();
visited[cent] = true;
for(int i = 0;i < v[cent].size();i++) if(!visited[v[cent][i]]) dnc(v[cent][i]);
}
int best_path(int N, int K, vector<vector<int> > H, vector<int> L){
n = N, k = K;
for(int i = 0;i < H.size();i++){
v[H[i][0]].push_back(H[i][1]);
c[H[i][0]].push_back(L[i]);
v[H[i][1]].push_back(H[i][0]);
c[H[i][1]].push_back(L[i]);
}
for(int i = 0;i <= K;i++) mindep[i] = newdep[i] = 1e9;
dnc(0);
return ans == 1e9 ? -1 : ans;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'int getSize(int, int)':
race.cpp:11:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for(int i = 0;i < v[x].size();i++){
| ~~^~~~~~~~~~~~~
race.cpp: In function 'int getCentroid(int, int, int)':
race.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0;i < v[x].size();i++){
| ~~^~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0;i < v[x].size();i++){
| ~~^~~~~~~~~~~~~
race.cpp: In function 'void dnc(int)':
race.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0;i < v[cent].size();i++){
| ~~^~~~~~~~~~~~~~~~
race.cpp:41:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int j = 0;j < chk1.size();j++) mindep[chk1[j]] = min(mindep[chk1[j]], newdep[chk1[j]]);
| ~~^~~~~~~~~~~~~
race.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int j = 0;j < chk2.size();j++) mindep[chk2[j]] = newdep[chk2[j]] = 1e9;
| ~~^~~~~~~~~~~~~
race.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0;i < v[cent].size();i++) if(!visited[v[cent][i]]) dnc(v[cent][i]);
| ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, std::vector<std::vector<int> >, std::vector<int>)':
race.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0;i < H.size();i++){
| ~~^~~~~~~~~~
/tmp/ccwDKJDJ.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status