이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "race.h"
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int mxN = 2e5 + 5;
const ll inf = 1e15;
ll dp[mxN][105];
vector<pi> adj[mxN];
void dfs(int x, int p) {
fill(dp[x], dp[x] + 105, inf);
dp[x][0] = 0;
for(auto [y, w] : adj[x]) {
if(y == p) continue;
dfs(y, x);
for(int j = w; j <= 100; ++j) {
dp[x][j] = min(dp[x][j], dp[y][j - w] + 1);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ll ans = inf;
for(int i = 0; i < N - 1; ++i) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
dfs(0, -1);
for(int i = 0; i < N; ++i) {
ans = min(ans, dp[i][K]);
}
return (ans < inf ? ans : -1);
}
# | 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... |