이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define int long long
int n;int k;
vector<pair<int,int>>e[200005];
int dp[1000006];
int sz[200005];
int iscen[200005];
int dfssz(int nw,int pa){
int ret=1;
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i].first;
if(v==pa||iscen[v]){continue;}
ret+=dfssz(v,nw);
}
sz[nw]=ret;
return ret;
}
void dfscen(int nw,int pa,int nd,int &pl){
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i].first;
if(v==pa||iscen[v]){continue;}
dfscen(v,nw,nd,pl);
}
if(pl==0&&sz[nw]>nd/2){
pl=nw;
}
}
int ans=1e8;
void dfs(int nw,int pa,int dis,int d,int ad){
if(dis<=k&&ad==0){
ans=min(ans,d+dp[k-dis]);
}
if(ad==1){
if(dis<=k){dp[dis]=min(dp[dis],d);}
}
if(ad==-1){
if(dis<=k){dp[dis]=1e7;}
}
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i].first;int w=e[nw][i].second;
if(iscen[v]||v==pa){continue;}
dfs(v,nw,dis+w,d+1,ad);
}
}
void solve(int rt){
int cen=0;
dfscen(rt,0,dfssz(rt,0),cen);
dp[0]=0;
for(int i=0;i<e[cen].size();i++){
int v=e[cen][i].first;int w=e[cen][i].second;
if(iscen[v]){continue;}
dfs(v,cen,w,1,0);
dfs(v,cen,w,1,1);
}
for(int i=0;i<e[cen].size();i++){
int v=e[cen][i].first;int w=e[cen][i].second;
if(iscen[v]){continue;}
dfs(v,cen,w,1,-1);
}
iscen[cen]=1;
for(int i=0;i<e[cen].size();i++){
int v=e[cen][i].first;int w=e[cen][i].second;
if(iscen[v]){continue;}
solve(v);
}
}
int best_path(int N, int K, int H[][2], int L[]){
cin>>n>>k;
for(int i=0;i<=k;i++){
dp[i]=1e7;
}
for(int i=1;i<=n-1;i++){
int a;int b;int c;
cin>>a>>b>>c;
a++;b++;
e[a].push_back({b,c});
e[b].push_back({a,c});
}
solve(1);
if(ans<=200000){
cout<<ans<<endl;
return ans;
}else{
cout<<-1<<endl;
return -1;
}
}
//signed main(){
//}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'long long int dfssz(long long int, long long int)':
race.cpp:12:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
race.cpp: In function 'void dfscen(long long int, long long int, long long int, long long int&)':
race.cpp:22:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
race.cpp: In function 'void dfs(long long int, long long int, long long int, long long int, long long int)':
race.cpp:42:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
race.cpp: In function 'void solve(long long int)':
race.cpp:54:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<e[cen].size();i++){
| ~^~~~~~~~~~~~~~
race.cpp:60:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i=0;i<e[cen].size();i++){
| ~^~~~~~~~~~~~~~
race.cpp:66:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=0;i<e[cen].size();i++){
| ~^~~~~~~~~~~~~~
race.cpp:67:31: warning: unused variable 'w' [-Wunused-variable]
67 | int v=e[cen][i].first;int w=e[cen][i].second;
| ^
/usr/bin/ld: /tmp/ccEIHXCX.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status