#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 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);
if(poss[u].size() > poss[v].size()) swap(poss[u], poss[v]);
for(auto [dis, cost]: poss[u]){
ll new_dis = dis + d;
if(new_dis > k) continue;
if(poss[v].count(k - dis - d)) {
res = min(poss[v][k - dis - d] + 1 + cost, res);
}
if(poss[v].count(new_dis))
poss[v][new_dis] = min(poss[v][new_dis], cost + 1);
else
poss[v][new_dis] = cost + 1;
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
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;
}
Compilation message
race.cpp: In function 'void dfs(ll, ll)':
race.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
21 | for(auto [u, d]: adj[v]){
| ^
race.cpp:25:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
25 | for(auto [dis, cost]: poss[u]){
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
18012 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
18012 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
18012 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
18012 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |