# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
100707 |
2019-03-13T14:58:29 Z |
arman_ferdous |
Race (IOI11_race) |
C++17 |
|
971 ms |
33272 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+10;
const int MAX = 1e6+10;
int n, k;
vector< pair<int,int> > g[200010];
int sub[N];
bool Deleted[N];
void dfs(int u, int f) {
sub[u] = 1;
for(auto it : g[u]) if(it.first != f && !Deleted[it.first]) {
dfs(it.first, u);
sub[u] += sub[it.first];
}
}
int get_centroid(int u, int f, int lim) {
int ret = -1;
for(auto it : g[u]) if(it.first != f && !Deleted[it.first]) {
if(sub[it.first] * 2 > lim) {
ret = get_centroid(it.first, u, lim);
break;
}
} if(ret == -1) return u;
return ret;
}
int F[MAX];
void reset_subtree(int u, int f, int cost) {
F[cost] = N + N;
for(auto it : g[u]) if(it.first != f && !Deleted[it.first] && cost + it.second <= k)
reset_subtree(it.first, u, cost + it.second);
}
int get_subtree(int u, int f, int cost, int cnt) {
int ret = N + N;
if(cost <= k) ret = F[k - cost] + cnt;
if(cost == k) ret = min(ret, cnt);
for(auto it : g[u]) if(it.first != f && !Deleted[it.first] && cost + it.second <= k)
ret = min(ret, get_subtree(it.first, u, cost + it.second, cnt + 1));
return ret;
}
void upd_subtree(int u, int f, int cost, int cnt) {
if(cost < MAX) F[cost] = min(F[cost], cnt);
for(auto it : g[u]) if(it.first != f && !Deleted[it.first] && cost + it.second <= k)
upd_subtree(it.first, u, cost + it.second, cnt + 1);
}
int calc(int u) {
int ans = N + N;
for(auto it : g[u]) if(!Deleted[it.first]) {
ans = min(ans, get_subtree(it.first, u, it.second, 1));
upd_subtree(it.first, u, it.second, 1);
}
for(auto it : g[u]) if(!Deleted[it.first]) reset_subtree(it.first, u, it.second);
return ans;
}
int solve(int s) {
dfs(s,-1);
int u = get_centroid(s, -1, sub[s]);
int ret = calc(u);
Deleted[u] = true;
for(auto it : g[u]) if(!Deleted[it.first])
ret = min(ret, solve(it.first));
return ret;
}
int best_path(int N_, int K, int H[][2], int L[]) {
n = N_; k = K;
for(int i = 0; i < n-1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
for(int i = 0; i <= k; i++) F[i] = N + N;
int ans = solve(0);
if(ans >= N+N) return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4864 KB |
Output is correct |
9 |
Correct |
6 ms |
4864 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
5120 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4864 KB |
Output is correct |
9 |
Correct |
6 ms |
4864 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
5120 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5168 KB |
Output is correct |
22 |
Correct |
10 ms |
8832 KB |
Output is correct |
23 |
Correct |
10 ms |
8704 KB |
Output is correct |
24 |
Correct |
10 ms |
8448 KB |
Output is correct |
25 |
Correct |
10 ms |
8320 KB |
Output is correct |
26 |
Correct |
8 ms |
6400 KB |
Output is correct |
27 |
Correct |
10 ms |
8192 KB |
Output is correct |
28 |
Correct |
9 ms |
5888 KB |
Output is correct |
29 |
Correct |
10 ms |
6400 KB |
Output is correct |
30 |
Correct |
9 ms |
6528 KB |
Output is correct |
31 |
Correct |
12 ms |
7680 KB |
Output is correct |
32 |
Correct |
9 ms |
7936 KB |
Output is correct |
33 |
Correct |
10 ms |
8192 KB |
Output is correct |
34 |
Correct |
9 ms |
7424 KB |
Output is correct |
35 |
Correct |
10 ms |
8320 KB |
Output is correct |
36 |
Correct |
11 ms |
8704 KB |
Output is correct |
37 |
Correct |
10 ms |
8320 KB |
Output is correct |
38 |
Correct |
9 ms |
7168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4864 KB |
Output is correct |
9 |
Correct |
6 ms |
4864 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
5120 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
191 ms |
10408 KB |
Output is correct |
20 |
Correct |
223 ms |
10436 KB |
Output is correct |
21 |
Correct |
224 ms |
10488 KB |
Output is correct |
22 |
Correct |
188 ms |
10488 KB |
Output is correct |
23 |
Correct |
122 ms |
10620 KB |
Output is correct |
24 |
Correct |
97 ms |
10488 KB |
Output is correct |
25 |
Correct |
219 ms |
13276 KB |
Output is correct |
26 |
Correct |
161 ms |
16084 KB |
Output is correct |
27 |
Correct |
237 ms |
15880 KB |
Output is correct |
28 |
Correct |
506 ms |
27276 KB |
Output is correct |
29 |
Correct |
491 ms |
26360 KB |
Output is correct |
30 |
Correct |
276 ms |
15888 KB |
Output is correct |
31 |
Correct |
240 ms |
15960 KB |
Output is correct |
32 |
Correct |
306 ms |
15992 KB |
Output is correct |
33 |
Correct |
406 ms |
14968 KB |
Output is correct |
34 |
Correct |
417 ms |
18696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
8 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4864 KB |
Output is correct |
9 |
Correct |
6 ms |
4864 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
5120 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5168 KB |
Output is correct |
22 |
Correct |
10 ms |
8832 KB |
Output is correct |
23 |
Correct |
10 ms |
8704 KB |
Output is correct |
24 |
Correct |
10 ms |
8448 KB |
Output is correct |
25 |
Correct |
10 ms |
8320 KB |
Output is correct |
26 |
Correct |
8 ms |
6400 KB |
Output is correct |
27 |
Correct |
10 ms |
8192 KB |
Output is correct |
28 |
Correct |
9 ms |
5888 KB |
Output is correct |
29 |
Correct |
10 ms |
6400 KB |
Output is correct |
30 |
Correct |
9 ms |
6528 KB |
Output is correct |
31 |
Correct |
12 ms |
7680 KB |
Output is correct |
32 |
Correct |
9 ms |
7936 KB |
Output is correct |
33 |
Correct |
10 ms |
8192 KB |
Output is correct |
34 |
Correct |
9 ms |
7424 KB |
Output is correct |
35 |
Correct |
10 ms |
8320 KB |
Output is correct |
36 |
Correct |
11 ms |
8704 KB |
Output is correct |
37 |
Correct |
10 ms |
8320 KB |
Output is correct |
38 |
Correct |
9 ms |
7168 KB |
Output is correct |
39 |
Correct |
191 ms |
10408 KB |
Output is correct |
40 |
Correct |
223 ms |
10436 KB |
Output is correct |
41 |
Correct |
224 ms |
10488 KB |
Output is correct |
42 |
Correct |
188 ms |
10488 KB |
Output is correct |
43 |
Correct |
122 ms |
10620 KB |
Output is correct |
44 |
Correct |
97 ms |
10488 KB |
Output is correct |
45 |
Correct |
219 ms |
13276 KB |
Output is correct |
46 |
Correct |
161 ms |
16084 KB |
Output is correct |
47 |
Correct |
237 ms |
15880 KB |
Output is correct |
48 |
Correct |
506 ms |
27276 KB |
Output is correct |
49 |
Correct |
491 ms |
26360 KB |
Output is correct |
50 |
Correct |
276 ms |
15888 KB |
Output is correct |
51 |
Correct |
240 ms |
15960 KB |
Output is correct |
52 |
Correct |
306 ms |
15992 KB |
Output is correct |
53 |
Correct |
406 ms |
14968 KB |
Output is correct |
54 |
Correct |
417 ms |
18696 KB |
Output is correct |
55 |
Correct |
17 ms |
5632 KB |
Output is correct |
56 |
Correct |
18 ms |
5632 KB |
Output is correct |
57 |
Correct |
119 ms |
10616 KB |
Output is correct |
58 |
Correct |
41 ms |
10704 KB |
Output is correct |
59 |
Correct |
113 ms |
16760 KB |
Output is correct |
60 |
Correct |
881 ms |
33272 KB |
Output is correct |
61 |
Correct |
321 ms |
19064 KB |
Output is correct |
62 |
Correct |
293 ms |
22904 KB |
Output is correct |
63 |
Correct |
399 ms |
22860 KB |
Output is correct |
64 |
Correct |
971 ms |
21192 KB |
Output is correct |
65 |
Correct |
411 ms |
23792 KB |
Output is correct |
66 |
Correct |
706 ms |
31300 KB |
Output is correct |
67 |
Correct |
185 ms |
23448 KB |
Output is correct |
68 |
Correct |
424 ms |
23672 KB |
Output is correct |
69 |
Correct |
363 ms |
23644 KB |
Output is correct |
70 |
Correct |
361 ms |
23032 KB |
Output is correct |