#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int bk[1000002], mn[1000002];
bool blocked[200001];
vector<ii> adj[200001];
int sz[200001], book = 1;
int ans = 1e9, K;
// Centroid
void dfs(int a, int p){
sz[a] = 1;
for(auto [x, w] : adj[a]){
if(blocked[x] || x == p) continue;
dfs(x, a);
sz[a] += sz[x];
}
}
void dfs_upd(int a, int p, long long wt, int ed){
for(auto [x, w] : adj[a]){
if(blocked[x] || x == p) continue;
int idx = int(min(1000001 * 1ll, wt + w));
bk[idx] = book; mn[idx] = mn[idx] == 0 ? ed : min(mn[idx], ed);
dfs_upd(x, a, wt + w, ed + 1);
}
}
void dfs_path(int a, int p, long long wt, int ed){
for(auto [x, w] : adj[a]){
if(blocked[x] || x == p) continue;
int idx = int(min(1000001 * 1ll, wt + w));
if(K - idx >= 0){
if(bk[K - idx] < book && bk[K - idx]) ans = min(ans, ed + mn[K - idx]);
}
dfs_path(x, a, wt + w, ed + 1);
if(ed == 1){
bk[idx] = book; mn[idx] = mn[idx] == 0 ? ed : min(mn[idx], ed);
dfs_upd(x, a, wt + w, ed + 1);
}
book++;
}
}
void dec(int a, int p){
dfs(a, a);
int cur = a, prev = -1;
while(true){
int mx = -1, nxt;
for(auto [x, w] : adj[cur]){
if(blocked[x] || x == prev) continue;
if(sz[x] > mx){
mx = sz[x];
nxt = x;
}
}
if(mx * 2 > sz[a]){
prev = cur;
cur = nxt;
}
else break;
}
blocked[cur] = true;
book = 1;
dfs_path(cur, cur, 0, 1);
memset(bk, 0, sizeof bk);
memset(mn, 0, sizeof mn);
for(auto [x, w]: adj[cur]) if(!blocked[x]) dec(x, cur);
}
int best_path(int N, int K_tmp, int H[][2], int L[])
{
K = K_tmp;
for(int i = 0; i < N - 1; i++){
adj[H[i][0]].push_back({H[i][1], L[i] * 1ll});
adj[H[i][1]].push_back({H[i][0], L[i] * 1ll});
}
dec(0, -1);
return ans == 1000000000 ? -1 : ans;
}
Compilation message
race.cpp: In function 'void dec(int, int)':
race.cpp:55:16: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
55 | int mx = -1, nxt;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
12836 KB |
Output is correct |
2 |
Correct |
48 ms |
12756 KB |
Output is correct |
3 |
Correct |
56 ms |
12816 KB |
Output is correct |
4 |
Correct |
49 ms |
12836 KB |
Output is correct |
5 |
Correct |
60 ms |
12836 KB |
Output is correct |
6 |
Correct |
49 ms |
12756 KB |
Output is correct |
7 |
Correct |
52 ms |
12820 KB |
Output is correct |
8 |
Incorrect |
59 ms |
12756 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
12836 KB |
Output is correct |
2 |
Correct |
48 ms |
12756 KB |
Output is correct |
3 |
Correct |
56 ms |
12816 KB |
Output is correct |
4 |
Correct |
49 ms |
12836 KB |
Output is correct |
5 |
Correct |
60 ms |
12836 KB |
Output is correct |
6 |
Correct |
49 ms |
12756 KB |
Output is correct |
7 |
Correct |
52 ms |
12820 KB |
Output is correct |
8 |
Incorrect |
59 ms |
12756 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
12836 KB |
Output is correct |
2 |
Correct |
48 ms |
12756 KB |
Output is correct |
3 |
Correct |
56 ms |
12816 KB |
Output is correct |
4 |
Correct |
49 ms |
12836 KB |
Output is correct |
5 |
Correct |
60 ms |
12836 KB |
Output is correct |
6 |
Correct |
49 ms |
12756 KB |
Output is correct |
7 |
Correct |
52 ms |
12820 KB |
Output is correct |
8 |
Incorrect |
59 ms |
12756 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
12836 KB |
Output is correct |
2 |
Correct |
48 ms |
12756 KB |
Output is correct |
3 |
Correct |
56 ms |
12816 KB |
Output is correct |
4 |
Correct |
49 ms |
12836 KB |
Output is correct |
5 |
Correct |
60 ms |
12836 KB |
Output is correct |
6 |
Correct |
49 ms |
12756 KB |
Output is correct |
7 |
Correct |
52 ms |
12820 KB |
Output is correct |
8 |
Incorrect |
59 ms |
12756 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |