# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1108192 |
2024-11-03T08:59:02 Z |
keunbum |
Race (IOI11_race) |
C++14 |
|
276 ms |
42856 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
int best_path(int N, int K, int H[][2], int L[]) {
int n = N;
int k = K;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; ++i) {
int x = H[i][0];
int y = H[i][1];
int z = L[i];
g[x].emplace_back(y, z);
g[y].emplace_back(x, z);
}
vector<bool> removed(n, false);
vector<int> sz(n);
vector<int> pv(n);
function<void(int)> DFS = [&](int v) -> void {
sz[v] = 1;
for (auto [u, _] : g[v]) {
if (u != pv[v] && !removed[u]) {
pv[u] = v;
DFS(u);
sz[v] += sz[u];
}
}
};
auto GetCenter = [&](int r) {
pv[r] = -1;
DFS(r);
int tot = sz[r];
while (true) {
int nr = -1;
for (auto [u, _] : g[r]) {
if (u != pv[r] && !removed[u] && sz[u] * 2 > tot) {
nr = u;
break;
}
}
if (nr == -1) {
return r;
}
r = nr;
}
};
int ans = n;
int iter = 0;
vector<int> aux(k + 1, 0);
vector<int> dp(k + 1, 0);
function<void(int, int, int, int)> Find = [&](int v, int pv, int dist, int depth) -> void {
if (dist > k) {
return;
}
if (aux[k - dist] == iter) {
ans = min(ans, dp[k - dist] + depth);
}
if (dist == k) {
ans = min(ans, depth);
}
for (auto [u, w] : g[v]) {
if (!removed[u] && u != pv) {
Find(u, v, dist + w, depth + 1);
}
}
};
function<void(int, int, int, int)> Calc = [&](int v, int pv, int dist, int depth) -> void {
if (dist > k) {
return;
}
if (aux[dist] < iter) {
aux[dist] = iter;
dp[dist] = depth;
} else
if (dp[dist] > depth) {
aux[dist] = iter;
dp[dist] = depth;
}
for (auto [u, w] : g[v]) {
if (!removed[u] && u != pv) {
Calc(u, v, dist + w, depth + 1);
}
}
};
function<void(int)> Solve = [&](int v) -> void {
v = GetCenter(v);
iter += 1;
for (auto [u, w] : g[v]) {
if (!removed[u]) {
Find(u, v, w, 1);
Calc(u, v, w, 1);
}
}
removed[v] = true;
for (auto [u, _] : g[v]) {
if (!removed[u]) {
Solve(u);
}
}
};
Solve(0);
return (ans == n ? -1 : ans);
}
Compilation message
race.cpp: In lambda function:
race.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for (auto [u, _] : g[v]) {
| ^
race.cpp: In lambda function:
race.cpp:41:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
41 | for (auto [u, _] : g[r]) {
| ^
race.cpp: In lambda function:
race.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | for (auto [u, w] : g[v]) {
| ^
race.cpp: In lambda function:
race.cpp:85:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for (auto [u, w] : g[v]) {
| ^
race.cpp: In lambda function:
race.cpp:94:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
94 | for (auto [u, w] : g[v]) {
| ^
race.cpp:101:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
101 | for (auto [u, _] : g[v]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Output is correct |
2 |
Correct |
1 ms |
2384 KB |
Output is correct |
3 |
Correct |
1 ms |
2384 KB |
Output is correct |
4 |
Correct |
1 ms |
2384 KB |
Output is correct |
5 |
Correct |
1 ms |
2384 KB |
Output is correct |
6 |
Correct |
1 ms |
2384 KB |
Output is correct |
7 |
Correct |
1 ms |
2384 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
1 ms |
2384 KB |
Output is correct |
10 |
Correct |
1 ms |
2608 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2384 KB |
Output is correct |
13 |
Correct |
1 ms |
2384 KB |
Output is correct |
14 |
Correct |
1 ms |
2384 KB |
Output is correct |
15 |
Correct |
1 ms |
2384 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2384 KB |
Output is correct |
18 |
Correct |
1 ms |
2384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Output is correct |
2 |
Correct |
1 ms |
2384 KB |
Output is correct |
3 |
Correct |
1 ms |
2384 KB |
Output is correct |
4 |
Correct |
1 ms |
2384 KB |
Output is correct |
5 |
Correct |
1 ms |
2384 KB |
Output is correct |
6 |
Correct |
1 ms |
2384 KB |
Output is correct |
7 |
Correct |
1 ms |
2384 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
1 ms |
2384 KB |
Output is correct |
10 |
Correct |
1 ms |
2608 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2384 KB |
Output is correct |
13 |
Correct |
1 ms |
2384 KB |
Output is correct |
14 |
Correct |
1 ms |
2384 KB |
Output is correct |
15 |
Correct |
1 ms |
2384 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2384 KB |
Output is correct |
18 |
Correct |
1 ms |
2384 KB |
Output is correct |
19 |
Correct |
1 ms |
2384 KB |
Output is correct |
20 |
Correct |
1 ms |
2384 KB |
Output is correct |
21 |
Correct |
1 ms |
2384 KB |
Output is correct |
22 |
Correct |
4 ms |
9552 KB |
Output is correct |
23 |
Correct |
3 ms |
8444 KB |
Output is correct |
24 |
Correct |
4 ms |
9296 KB |
Output is correct |
25 |
Correct |
4 ms |
9040 KB |
Output is correct |
26 |
Correct |
3 ms |
5200 KB |
Output is correct |
27 |
Correct |
3 ms |
8784 KB |
Output is correct |
28 |
Correct |
2 ms |
3920 KB |
Output is correct |
29 |
Correct |
3 ms |
4944 KB |
Output is correct |
30 |
Correct |
3 ms |
5200 KB |
Output is correct |
31 |
Correct |
2 ms |
7504 KB |
Output is correct |
32 |
Correct |
3 ms |
8016 KB |
Output is correct |
33 |
Correct |
4 ms |
8528 KB |
Output is correct |
34 |
Correct |
3 ms |
6992 KB |
Output is correct |
35 |
Correct |
3 ms |
8784 KB |
Output is correct |
36 |
Correct |
4 ms |
9808 KB |
Output is correct |
37 |
Correct |
3 ms |
8784 KB |
Output is correct |
38 |
Correct |
4 ms |
6480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Output is correct |
2 |
Correct |
1 ms |
2384 KB |
Output is correct |
3 |
Correct |
1 ms |
2384 KB |
Output is correct |
4 |
Correct |
1 ms |
2384 KB |
Output is correct |
5 |
Correct |
1 ms |
2384 KB |
Output is correct |
6 |
Correct |
1 ms |
2384 KB |
Output is correct |
7 |
Correct |
1 ms |
2384 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
1 ms |
2384 KB |
Output is correct |
10 |
Correct |
1 ms |
2608 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2384 KB |
Output is correct |
13 |
Correct |
1 ms |
2384 KB |
Output is correct |
14 |
Correct |
1 ms |
2384 KB |
Output is correct |
15 |
Correct |
1 ms |
2384 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2384 KB |
Output is correct |
18 |
Correct |
1 ms |
2384 KB |
Output is correct |
19 |
Correct |
88 ms |
11352 KB |
Output is correct |
20 |
Correct |
88 ms |
11344 KB |
Output is correct |
21 |
Correct |
97 ms |
11368 KB |
Output is correct |
22 |
Correct |
87 ms |
11600 KB |
Output is correct |
23 |
Correct |
67 ms |
11600 KB |
Output is correct |
24 |
Correct |
42 ms |
11600 KB |
Output is correct |
25 |
Correct |
94 ms |
15692 KB |
Output is correct |
26 |
Correct |
87 ms |
20304 KB |
Output is correct |
27 |
Correct |
96 ms |
18504 KB |
Output is correct |
28 |
Correct |
172 ms |
35912 KB |
Output is correct |
29 |
Correct |
172 ms |
34376 KB |
Output is correct |
30 |
Correct |
102 ms |
18540 KB |
Output is correct |
31 |
Correct |
99 ms |
18504 KB |
Output is correct |
32 |
Correct |
114 ms |
18520 KB |
Output is correct |
33 |
Correct |
144 ms |
17480 KB |
Output is correct |
34 |
Correct |
125 ms |
17252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Output is correct |
2 |
Correct |
1 ms |
2384 KB |
Output is correct |
3 |
Correct |
1 ms |
2384 KB |
Output is correct |
4 |
Correct |
1 ms |
2384 KB |
Output is correct |
5 |
Correct |
1 ms |
2384 KB |
Output is correct |
6 |
Correct |
1 ms |
2384 KB |
Output is correct |
7 |
Correct |
1 ms |
2384 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
1 ms |
2384 KB |
Output is correct |
10 |
Correct |
1 ms |
2608 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2384 KB |
Output is correct |
13 |
Correct |
1 ms |
2384 KB |
Output is correct |
14 |
Correct |
1 ms |
2384 KB |
Output is correct |
15 |
Correct |
1 ms |
2384 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2384 KB |
Output is correct |
18 |
Correct |
1 ms |
2384 KB |
Output is correct |
19 |
Correct |
1 ms |
2384 KB |
Output is correct |
20 |
Correct |
1 ms |
2384 KB |
Output is correct |
21 |
Correct |
1 ms |
2384 KB |
Output is correct |
22 |
Correct |
4 ms |
9552 KB |
Output is correct |
23 |
Correct |
3 ms |
8444 KB |
Output is correct |
24 |
Correct |
4 ms |
9296 KB |
Output is correct |
25 |
Correct |
4 ms |
9040 KB |
Output is correct |
26 |
Correct |
3 ms |
5200 KB |
Output is correct |
27 |
Correct |
3 ms |
8784 KB |
Output is correct |
28 |
Correct |
2 ms |
3920 KB |
Output is correct |
29 |
Correct |
3 ms |
4944 KB |
Output is correct |
30 |
Correct |
3 ms |
5200 KB |
Output is correct |
31 |
Correct |
2 ms |
7504 KB |
Output is correct |
32 |
Correct |
3 ms |
8016 KB |
Output is correct |
33 |
Correct |
4 ms |
8528 KB |
Output is correct |
34 |
Correct |
3 ms |
6992 KB |
Output is correct |
35 |
Correct |
3 ms |
8784 KB |
Output is correct |
36 |
Correct |
4 ms |
9808 KB |
Output is correct |
37 |
Correct |
3 ms |
8784 KB |
Output is correct |
38 |
Correct |
4 ms |
6480 KB |
Output is correct |
39 |
Correct |
88 ms |
11352 KB |
Output is correct |
40 |
Correct |
88 ms |
11344 KB |
Output is correct |
41 |
Correct |
97 ms |
11368 KB |
Output is correct |
42 |
Correct |
87 ms |
11600 KB |
Output is correct |
43 |
Correct |
67 ms |
11600 KB |
Output is correct |
44 |
Correct |
42 ms |
11600 KB |
Output is correct |
45 |
Correct |
94 ms |
15692 KB |
Output is correct |
46 |
Correct |
87 ms |
20304 KB |
Output is correct |
47 |
Correct |
96 ms |
18504 KB |
Output is correct |
48 |
Correct |
172 ms |
35912 KB |
Output is correct |
49 |
Correct |
172 ms |
34376 KB |
Output is correct |
50 |
Correct |
102 ms |
18540 KB |
Output is correct |
51 |
Correct |
99 ms |
18504 KB |
Output is correct |
52 |
Correct |
114 ms |
18520 KB |
Output is correct |
53 |
Correct |
144 ms |
17480 KB |
Output is correct |
54 |
Correct |
125 ms |
17252 KB |
Output is correct |
55 |
Correct |
9 ms |
3152 KB |
Output is correct |
56 |
Correct |
8 ms |
3152 KB |
Output is correct |
57 |
Correct |
62 ms |
11772 KB |
Output is correct |
58 |
Correct |
25 ms |
11716 KB |
Output is correct |
59 |
Correct |
88 ms |
21604 KB |
Output is correct |
60 |
Correct |
276 ms |
42856 KB |
Output is correct |
61 |
Correct |
106 ms |
18580 KB |
Output is correct |
62 |
Correct |
129 ms |
26216 KB |
Output is correct |
63 |
Correct |
141 ms |
26228 KB |
Output is correct |
64 |
Correct |
247 ms |
22088 KB |
Output is correct |
65 |
Correct |
122 ms |
18280 KB |
Output is correct |
66 |
Correct |
242 ms |
39240 KB |
Output is correct |
67 |
Correct |
67 ms |
27064 KB |
Output is correct |
68 |
Correct |
147 ms |
26172 KB |
Output is correct |
69 |
Correct |
144 ms |
26468 KB |
Output is correct |
70 |
Correct |
125 ms |
25804 KB |
Output is correct |