#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define pb push_back
#define fi first
#define se second
using ll = long long;
using ld = long double;
using pii = pair<ll, ll>;
const int MAXN = 2e5 + 5;
vector<pii> adj[MAXN];
map<ll, ll> poss[MAXN];
ll off[MAXN];
ll res = 1e18;
int k;
void dfs(ll v, ll p){
poss[v][0] = 0;
for(auto [u, d]: adj[v]){
if(u == p) continue;
dfs(u, v);
off[u] += d;
if(poss[u].size() > poss[v].size()) {
swap(off[u], off[v]);
swap(poss[u], poss[v]);
}
for(auto [dis, cost]: poss[u]){
ll real_dis = dis + off[u];
if(real_dis + off[v] > k) continue;
if(poss[v].count(k - off[v] - real_dis)){
res = min(poss[v][k - off[v] - real_dis] + 1 + cost, res);
}
real_dis -= off[v];
if(poss[v].count(real_dis))
poss[v][real_dis] = min(poss[v][real_dis], cost + 1);
else
poss[v][real_dis] = cost + 1;
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
rep(i, 0, N) {
adj[i] = {};
poss[i] = {};
off[i] = 0;
}
k = K;
rep(i, 0, N - 1) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
dfs(0, -1);
if(res < 1e18) return res;
else return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
19548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
19548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
19548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
19548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |