# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
418700 |
2021-06-05T18:49:44 Z |
snasibov05 |
Race (IOI11_race) |
C++14 |
|
1022 ms |
50368 KB |
#include "race.h"
#include <vector>
#include <map>
using namespace std;
#define oo 1000000000
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
int ans = oo;
const int nmax = 2e5 + 5;
vector<pii> ed[nmax];
bool used[nmax];
int size[nmax];
vector<pii> v;
void calcSize(int cur, int pr){
size[cur] = 1;
for (auto [x, w] : ed[cur]){
if (used[x] || x == pr) continue;
calcSize(x, cur);
size[cur] += size[x];
}
}
int findCentroid(int cur, int pr, int n){
for (auto [x, w] : ed[cur]){
if (used[x] || x == pr) continue;
if (size[x] > n / 2){
return findCentroid(x, cur, n);
}
}
return cur;
}
void dfs(int cur, int pr, int k, int d, int l){
if (d > k) return;
v.pb({d, l});
for (auto [x, w] : ed[cur]){
if (x == pr || used[x]) continue;
dfs(x, cur, k, d + w, l + 1);
}
}
void calc(int cur, int k){
calcSize(cur, -1);
cur = findCentroid(cur, -1, size[cur]);
map<int, int> dp;
used[cur] = true;
for (auto [x, w] : ed[cur]){
if (used[x]) continue;
v.clear();
dfs(x, cur, k, w, 1);
for (auto [d, l] : v){
if (d == k) ans = min(ans, l);
if (dp.count(k-d) == 0) continue;
ans = min(ans, l + dp[k - d]);
}
for (auto [d, l] : v){
if (dp[d] == 0) dp[d] = l;
else dp[d] = min(dp[d], l);
}
}
for (auto [x, w] : ed[cur]){
if (used[x]) continue;
calc(x, k);
}
}
int best_path(int n, int k, int h[][2], int l[]){
for (int i = 0; i < n - 1; ++i) {
ed[h[i][0]].pb({h[i][1], l[i]});
ed[h[i][1]].pb({h[i][0], l[i]});
}
calc(0, k);
if (ans == oo) ans = -1;
return ans;
}
Compilation message
race.cpp: In function 'void calcSize(int, int)':
race.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
22 | for (auto [x, w] : ed[cur]){
| ^
race.cpp: In function 'int findCentroid(int, int, int)':
race.cpp:30:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for (auto [x, w] : ed[cur]){
| ^
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for (auto [x, w] : ed[cur]){
| ^
race.cpp: In function 'void calc(int, int)':
race.cpp:55:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for (auto [x, w] : ed[cur]){
| ^
race.cpp:60:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for (auto [d, l] : v){
| ^
race.cpp:65:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | for (auto [d, l] : v){
| ^
race.cpp:71:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
71 | for (auto [x, w] : ed[cur]){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4956 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4952 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4956 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4952 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
4 ms |
4940 KB |
Output is correct |
21 |
Correct |
4 ms |
5068 KB |
Output is correct |
22 |
Correct |
4 ms |
4940 KB |
Output is correct |
23 |
Correct |
3 ms |
4940 KB |
Output is correct |
24 |
Correct |
4 ms |
4940 KB |
Output is correct |
25 |
Correct |
5 ms |
5132 KB |
Output is correct |
26 |
Correct |
5 ms |
4940 KB |
Output is correct |
27 |
Correct |
3 ms |
4940 KB |
Output is correct |
28 |
Correct |
4 ms |
5068 KB |
Output is correct |
29 |
Correct |
6 ms |
5068 KB |
Output is correct |
30 |
Correct |
5 ms |
5068 KB |
Output is correct |
31 |
Correct |
5 ms |
5068 KB |
Output is correct |
32 |
Correct |
5 ms |
5068 KB |
Output is correct |
33 |
Correct |
5 ms |
5068 KB |
Output is correct |
34 |
Correct |
4 ms |
5068 KB |
Output is correct |
35 |
Correct |
5 ms |
5068 KB |
Output is correct |
36 |
Correct |
4 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
5 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4956 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4952 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
208 ms |
10456 KB |
Output is correct |
20 |
Correct |
201 ms |
10520 KB |
Output is correct |
21 |
Correct |
211 ms |
10608 KB |
Output is correct |
22 |
Correct |
216 ms |
10884 KB |
Output is correct |
23 |
Correct |
93 ms |
10640 KB |
Output is correct |
24 |
Correct |
85 ms |
10344 KB |
Output is correct |
25 |
Correct |
151 ms |
13856 KB |
Output is correct |
26 |
Correct |
124 ms |
18028 KB |
Output is correct |
27 |
Correct |
223 ms |
15812 KB |
Output is correct |
28 |
Correct |
301 ms |
30124 KB |
Output is correct |
29 |
Correct |
300 ms |
28992 KB |
Output is correct |
30 |
Correct |
225 ms |
15872 KB |
Output is correct |
31 |
Correct |
221 ms |
15812 KB |
Output is correct |
32 |
Correct |
249 ms |
15792 KB |
Output is correct |
33 |
Correct |
318 ms |
14916 KB |
Output is correct |
34 |
Correct |
184 ms |
14656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4956 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4952 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
4 ms |
4940 KB |
Output is correct |
21 |
Correct |
4 ms |
5068 KB |
Output is correct |
22 |
Correct |
4 ms |
4940 KB |
Output is correct |
23 |
Correct |
3 ms |
4940 KB |
Output is correct |
24 |
Correct |
4 ms |
4940 KB |
Output is correct |
25 |
Correct |
5 ms |
5132 KB |
Output is correct |
26 |
Correct |
5 ms |
4940 KB |
Output is correct |
27 |
Correct |
3 ms |
4940 KB |
Output is correct |
28 |
Correct |
4 ms |
5068 KB |
Output is correct |
29 |
Correct |
6 ms |
5068 KB |
Output is correct |
30 |
Correct |
5 ms |
5068 KB |
Output is correct |
31 |
Correct |
5 ms |
5068 KB |
Output is correct |
32 |
Correct |
5 ms |
5068 KB |
Output is correct |
33 |
Correct |
5 ms |
5068 KB |
Output is correct |
34 |
Correct |
4 ms |
5068 KB |
Output is correct |
35 |
Correct |
5 ms |
5068 KB |
Output is correct |
36 |
Correct |
4 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
5 ms |
5068 KB |
Output is correct |
39 |
Correct |
208 ms |
10456 KB |
Output is correct |
40 |
Correct |
201 ms |
10520 KB |
Output is correct |
41 |
Correct |
211 ms |
10608 KB |
Output is correct |
42 |
Correct |
216 ms |
10884 KB |
Output is correct |
43 |
Correct |
93 ms |
10640 KB |
Output is correct |
44 |
Correct |
85 ms |
10344 KB |
Output is correct |
45 |
Correct |
151 ms |
13856 KB |
Output is correct |
46 |
Correct |
124 ms |
18028 KB |
Output is correct |
47 |
Correct |
223 ms |
15812 KB |
Output is correct |
48 |
Correct |
301 ms |
30124 KB |
Output is correct |
49 |
Correct |
300 ms |
28992 KB |
Output is correct |
50 |
Correct |
225 ms |
15872 KB |
Output is correct |
51 |
Correct |
221 ms |
15812 KB |
Output is correct |
52 |
Correct |
249 ms |
15792 KB |
Output is correct |
53 |
Correct |
318 ms |
14916 KB |
Output is correct |
54 |
Correct |
184 ms |
14656 KB |
Output is correct |
55 |
Correct |
22 ms |
5872 KB |
Output is correct |
56 |
Correct |
18 ms |
5632 KB |
Output is correct |
57 |
Correct |
151 ms |
10992 KB |
Output is correct |
58 |
Correct |
53 ms |
10476 KB |
Output is correct |
59 |
Correct |
330 ms |
26332 KB |
Output is correct |
60 |
Correct |
982 ms |
50368 KB |
Output is correct |
61 |
Correct |
302 ms |
19192 KB |
Output is correct |
62 |
Correct |
322 ms |
18984 KB |
Output is correct |
63 |
Correct |
383 ms |
19012 KB |
Output is correct |
64 |
Correct |
1022 ms |
30900 KB |
Output is correct |
65 |
Correct |
236 ms |
19644 KB |
Output is correct |
66 |
Correct |
641 ms |
31088 KB |
Output is correct |
67 |
Correct |
141 ms |
19552 KB |
Output is correct |
68 |
Correct |
442 ms |
26436 KB |
Output is correct |
69 |
Correct |
471 ms |
26812 KB |
Output is correct |
70 |
Correct |
451 ms |
25712 KB |
Output is correct |