이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
struct edge{
int u;
int l;
};
int N,K;
vector<vector<edge> > s;
int best;
vector<int> pathssmallK(int x, int p){
vector<int> possible(K+1, N);
possible[0] = 0;
for (int i=0;i<s[x].size();i++){
if (s[x][i].u == p) continue;
vector<int> pths = pathssmallK(s[x][i].u, x);
for (int j=0;j<=K;j++){
if (pths[j] == N) continue;
if (j + s[x][i].l > K) continue;
if (possible[K - j - s[x][i].l] != N){
best = min(best, possible[K - j - s[x][i].l] + 1 + pths[j]);
}
}
for (int j=0;j<=K;j++){
if (pths[j] == N) continue;
if (j + s[x][i].l > K) continue;
possible[j + s[x][i].l] = min(possible[j + s[x][i].l], 1 + pths[j]);
}
}
/*cout << x << ": ";
for (int i=0;i<K+1;i++) cout << possible[i] << " ";
cout << endl;*/
return possible;
}
map<int,int> paths(int x, int p){
map<int,int> possible;
possible[0] = 0;
for (int i=0;i<s[x].size();i++){
if (s[x][i].u == p) continue;
map<int, int> pths = paths(s[x][i].u, x);
int l = s[x][i].l;
for (map<int,int>::iterator it = pths.begin(); it != pths.end(); it++){
if (possible.count(K - l - it -> first) > 0){
best = min(best, 1 + it -> second + possible[K - l - it -> first]);
}
}
for (map<int,int>::iterator it = pths.begin(); it != pths.end(); it++){
if (l + it -> second > K) continue;
if (possible.count(l + it -> second) > 0)
possible[l + it -> second] = min(possible[l + it -> second], 1 + it -> second); else possible[l + it -> second] = 1 + it -> second;
}
}
/* cout << x << ": " << endl;
for (map<int,int>::iterator it = possible.begin(); it != possible.end(); it++) cout << it -> first << " " << it -> second << endl;
cout << endl; */
return possible;
}
int best_path(int _N, int _K, int H[][2], int L[]){
N = _N; K = _K;
s.assign(N, vector<edge> ());
for (int i=0;i<N-1;i++){
edge e,f;
e.l = L[i];
e.u = H[i][0];
f.l = L[i];
f.u = H[i][1];
s[H[i][1]].push_back(e);
s[H[i][0]].push_back(f);
}
best = N;
if (K <= 100) pathssmallK(0, -1); else
paths(0, -1);
if (best == N) return -1; else return best;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'std::vector<int> pathssmallK(int, int)':
race.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i=0;i<s[x].size();i++){
| ~^~~~~~~~~~~~
race.cpp: In function 'std::map<int, int> paths(int, int)':
race.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i=0;i<s[x].size();i++){
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |