#include "race.h"
#include <bits/stdc++.h>
constexpr int N = 2e5;
int n, k, ans = 1e9;
int siz[N], del[N];
std::vector<std::pair<int, int>> path;
std::vector<std::vector<std::pair<int, int>>> e(N);
int dfs(int u, int p = -1) {
siz[u] = 1;
for (auto [v, w] : e[u]) {
if (del[v] || v == p)
continue;
siz[u] += dfs(v, u);
}
return siz[u];
}
void dfs2(int u, int dep, int len, int p) {
path.emplace_back(len, dep);
for (auto [v, w] : e[u]) {
if (del[v] || v == p)
continue;
dfs2(v, dep + 1, len + w, u);
}
}
int Cen(int u, int S, int p = -1) {
for (auto [v, w] : e[u]) {
if (del[v] || v == p)
continue;
if (2 * siz[v] > S)
return Cen(v, S, u);
}
return u;
}
void Decompose(int u) {
int c = Cen(u, dfs(u));
std::map<int, int> dp, vis;
vis[0] = 1;
for (auto [v, w] : e[c]) {
if (del[v])
continue;
path.clear();
dfs2(v, 1, w, c);
for (auto [len, dep] : path) {
if (len > k)
continue;
if (vis[k - len])
ans = std::min(ans, dep + dp[k - len]);
}
for (auto [len, dep] : path) {
if (len > k)
continue;
if (vis[len] == 0 || dep < dp[len])
dp[len] = dep;
vis[len] = 1;
}
}
del[c] = 1;
for (auto [v, w] : e[c]) {
if (!del[v])
Decompose(v);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 0; i < n - 1; i++) {
int u = H[i][0], v = H[i][1], w = L[i];
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
Decompose(0);
return ans == 1e9 ? -1 : ans;
}
// int main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cin >> n >> k;
// for (int i = 0; i < n - 1; i++) {
// int u, v, w;
// std::cin >> u >> v >> w;
// e[u].emplace_back(v, w);
// e[v].emplace_back(u, w);
// }
// Decompose(0);
// std::cout << (ans == 1e9 ? -1 : ans) << '\n';
// }
Compilation message
race.cpp: In function 'int dfs(int, int)':
race.cpp:10:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
10 | for (auto [v, w] : e[u]) {
| ^
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
19 | for (auto [v, w] : e[u]) {
| ^
race.cpp: In function 'int Cen(int, int, int)':
race.cpp:26:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | for (auto [v, w] : e[u]) {
| ^
race.cpp: In function 'void Decompose(int)':
race.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | for (auto [v, w] : e[c]) {
| ^
race.cpp:43:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
43 | for (auto [len, dep] : path) {
| ^
race.cpp:49:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
49 | for (auto [len, dep] : path) {
| ^
race.cpp:58:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | for (auto [v, w] : e[c]) {
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 11 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 13 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 14 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 16 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 17 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 18 |
Correct |
4 ms |
5100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 11 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 13 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 14 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 16 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 17 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 18 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 19 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 20 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 21 |
Correct |
8 ms |
5228 KB |
Output is correct |
| 22 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 23 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 24 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 25 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 26 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 27 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 28 |
Correct |
6 ms |
5228 KB |
Output is correct |
| 29 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 30 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 31 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 32 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 33 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 34 |
Correct |
6 ms |
5228 KB |
Output is correct |
| 35 |
Correct |
6 ms |
5228 KB |
Output is correct |
| 36 |
Correct |
6 ms |
5228 KB |
Output is correct |
| 37 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 38 |
Correct |
7 ms |
5356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 11 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 13 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 14 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 16 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 17 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 18 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 19 |
Correct |
357 ms |
12520 KB |
Output is correct |
| 20 |
Correct |
387 ms |
12520 KB |
Output is correct |
| 21 |
Correct |
361 ms |
12668 KB |
Output is correct |
| 22 |
Correct |
379 ms |
12644 KB |
Output is correct |
| 23 |
Correct |
196 ms |
12776 KB |
Output is correct |
| 24 |
Correct |
132 ms |
12524 KB |
Output is correct |
| 25 |
Correct |
229 ms |
15340 KB |
Output is correct |
| 26 |
Correct |
139 ms |
18284 KB |
Output is correct |
| 27 |
Correct |
357 ms |
18156 KB |
Output is correct |
| 28 |
Correct |
590 ms |
30304 KB |
Output is correct |
| 29 |
Correct |
558 ms |
29280 KB |
Output is correct |
| 30 |
Correct |
373 ms |
17900 KB |
Output is correct |
| 31 |
Correct |
361 ms |
18028 KB |
Output is correct |
| 32 |
Correct |
482 ms |
18068 KB |
Output is correct |
| 33 |
Correct |
621 ms |
17760 KB |
Output is correct |
| 34 |
Correct |
392 ms |
17580 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 11 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 13 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 14 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 16 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 17 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 18 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 19 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 20 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 21 |
Correct |
8 ms |
5228 KB |
Output is correct |
| 22 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 23 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 24 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 25 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 26 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 27 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 28 |
Correct |
6 ms |
5228 KB |
Output is correct |
| 29 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 30 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 31 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 32 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 33 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 34 |
Correct |
6 ms |
5228 KB |
Output is correct |
| 35 |
Correct |
6 ms |
5228 KB |
Output is correct |
| 36 |
Correct |
6 ms |
5228 KB |
Output is correct |
| 37 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 38 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 39 |
Correct |
357 ms |
12520 KB |
Output is correct |
| 40 |
Correct |
387 ms |
12520 KB |
Output is correct |
| 41 |
Correct |
361 ms |
12668 KB |
Output is correct |
| 42 |
Correct |
379 ms |
12644 KB |
Output is correct |
| 43 |
Correct |
196 ms |
12776 KB |
Output is correct |
| 44 |
Correct |
132 ms |
12524 KB |
Output is correct |
| 45 |
Correct |
229 ms |
15340 KB |
Output is correct |
| 46 |
Correct |
139 ms |
18284 KB |
Output is correct |
| 47 |
Correct |
357 ms |
18156 KB |
Output is correct |
| 48 |
Correct |
590 ms |
30304 KB |
Output is correct |
| 49 |
Correct |
558 ms |
29280 KB |
Output is correct |
| 50 |
Correct |
373 ms |
17900 KB |
Output is correct |
| 51 |
Correct |
361 ms |
18028 KB |
Output is correct |
| 52 |
Correct |
482 ms |
18068 KB |
Output is correct |
| 53 |
Correct |
621 ms |
17760 KB |
Output is correct |
| 54 |
Correct |
392 ms |
17580 KB |
Output is correct |
| 55 |
Correct |
40 ms |
6764 KB |
Output is correct |
| 56 |
Correct |
25 ms |
5868 KB |
Output is correct |
| 57 |
Correct |
269 ms |
12696 KB |
Output is correct |
| 58 |
Correct |
71 ms |
12000 KB |
Output is correct |
| 59 |
Correct |
758 ms |
39148 KB |
Output is correct |
| 60 |
Correct |
2180 ms |
81752 KB |
Output is correct |
| 61 |
Correct |
521 ms |
20204 KB |
Output is correct |
| 62 |
Correct |
565 ms |
20164 KB |
Output is correct |
| 63 |
Correct |
669 ms |
20204 KB |
Output is correct |
| 64 |
Correct |
2253 ms |
54036 KB |
Output is correct |
| 65 |
Correct |
409 ms |
21224 KB |
Output is correct |
| 66 |
Correct |
1483 ms |
33220 KB |
Output is correct |
| 67 |
Correct |
196 ms |
20316 KB |
Output is correct |
| 68 |
Correct |
871 ms |
41604 KB |
Output is correct |
| 69 |
Correct |
915 ms |
41956 KB |
Output is correct |
| 70 |
Correct |
839 ms |
40544 KB |
Output is correct |
