# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
120224 |
2019-06-24T01:56:09 Z |
joseacaz |
Race (IOI11_race) |
C++17 |
|
623 ms |
35960 KB |
#include "race.h"
#include <bits/stdc++.h>
#define MAXN 200005
#define MAXK 1000005
#define INF (1 << 30)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int N, K, H[MAXN][2], L[MAXN], dead[MAXN], sz[MAXN], DP[MAXK], vis[MAXK], C;
vector < pii > Graph[MAXN];
int precalc ( int node, int p = -1 )
{
sz[node] = 1;
for ( auto i : Graph[node] )
if ( !dead[i.first] && i.first != p )
sz[node] += precalc ( i.first, node );
return sz[node];
}
int find_centroid ( int node, int siz, int p = -1 )
{
for ( auto i : Graph[node] )
if ( !dead[i.first] && i.first != p && 2 * sz[i.first] > siz )
return find_centroid ( i.first, siz, node );
return node;
}
int qry ( int node, int p, int depth, int cost )
{
if ( cost > K )
return INF;
int aux = INF;
if ( vis[K - cost] == C )
aux = DP[K - cost] + depth;
for ( auto i : Graph[node] )
if ( !dead[i.first] && i.first != p )
aux = min ( aux, qry ( i.first, node, depth + 1, cost + i.second ) );
return aux;
}
void upd ( int node, int p, int depth, int cost )
{
if ( cost > K )
return;
if ( vis[cost] != C )
DP[cost] = depth;
vis[cost] = C;
DP[cost] = min ( DP[cost], depth );
for ( auto i : Graph[node] )
if ( !dead[i.first] && i.first != p )
upd ( i.first, node, depth + 1, cost + i.second );
}
int solve ( int node )
{
precalc ( node );
node = find_centroid ( node, sz[node] );
dead[node] = 1;
int aux = INF;
C++;
vis[0] = C, DP[0] = 0;
for ( auto i : Graph[node] )
{
if ( !dead[i.first] )
{
aux = min ( aux, qry ( i.first, node, 1, i.second ) );
upd ( i.first, node, 1, i.second );
}
}
for ( auto i : Graph[node] )
if ( !dead[i.first] )
aux = min ( aux, solve ( i.first ) );
return aux;
}
int best_path ( int _n, int _k, int _h[][2], int _l[] )
{
N = _n;
K = _k;
for ( int i = 0; i < N - 1; i++ )
{
H[i][0] = _h[i][0];
H[i][1] = _h[i][1];
L[i] = _l[i];
Graph[H[i][0]].push_back ( {H[i][1], L[i]} );
Graph[H[i][1]].push_back ( {H[i][0], L[i]} );
}
int ans = solve ( 0 );
return (ans != INF ? ans : -1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
6 ms |
5120 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
5 ms |
5120 KB |
Output is correct |
5 |
Correct |
6 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
6 ms |
5120 KB |
Output is correct |
8 |
Correct |
6 ms |
5120 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
7 ms |
5120 KB |
Output is correct |
11 |
Correct |
6 ms |
5120 KB |
Output is correct |
12 |
Correct |
6 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 |
5120 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
6 ms |
5120 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
5 ms |
5120 KB |
Output is correct |
5 |
Correct |
6 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
6 ms |
5120 KB |
Output is correct |
8 |
Correct |
6 ms |
5120 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
7 ms |
5120 KB |
Output is correct |
11 |
Correct |
6 ms |
5120 KB |
Output is correct |
12 |
Correct |
6 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 |
5120 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
9 ms |
5120 KB |
Output is correct |
22 |
Correct |
12 ms |
10112 KB |
Output is correct |
23 |
Correct |
11 ms |
9472 KB |
Output is correct |
24 |
Correct |
12 ms |
10880 KB |
Output is correct |
25 |
Correct |
11 ms |
8704 KB |
Output is correct |
26 |
Correct |
9 ms |
7808 KB |
Output is correct |
27 |
Correct |
6 ms |
5120 KB |
Output is correct |
28 |
Correct |
8 ms |
6784 KB |
Output is correct |
29 |
Correct |
9 ms |
7680 KB |
Output is correct |
30 |
Correct |
10 ms |
7936 KB |
Output is correct |
31 |
Correct |
11 ms |
8704 KB |
Output is correct |
32 |
Correct |
10 ms |
8804 KB |
Output is correct |
33 |
Correct |
12 ms |
10496 KB |
Output is correct |
34 |
Correct |
12 ms |
9600 KB |
Output is correct |
35 |
Correct |
12 ms |
11008 KB |
Output is correct |
36 |
Correct |
12 ms |
11648 KB |
Output is correct |
37 |
Correct |
10 ms |
8960 KB |
Output is correct |
38 |
Correct |
9 ms |
7552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
6 ms |
5120 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
5 ms |
5120 KB |
Output is correct |
5 |
Correct |
6 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
6 ms |
5120 KB |
Output is correct |
8 |
Correct |
6 ms |
5120 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
7 ms |
5120 KB |
Output is correct |
11 |
Correct |
6 ms |
5120 KB |
Output is correct |
12 |
Correct |
6 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 |
5120 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
134 ms |
13244 KB |
Output is correct |
20 |
Correct |
138 ms |
13384 KB |
Output is correct |
21 |
Correct |
146 ms |
13296 KB |
Output is correct |
22 |
Correct |
131 ms |
13376 KB |
Output is correct |
23 |
Correct |
89 ms |
13560 KB |
Output is correct |
24 |
Correct |
81 ms |
13432 KB |
Output is correct |
25 |
Correct |
148 ms |
15224 KB |
Output is correct |
26 |
Correct |
93 ms |
17400 KB |
Output is correct |
27 |
Correct |
194 ms |
21760 KB |
Output is correct |
28 |
Correct |
365 ms |
30196 KB |
Output is correct |
29 |
Correct |
376 ms |
29388 KB |
Output is correct |
30 |
Correct |
217 ms |
22008 KB |
Output is correct |
31 |
Correct |
195 ms |
21752 KB |
Output is correct |
32 |
Correct |
233 ms |
21880 KB |
Output is correct |
33 |
Correct |
325 ms |
20728 KB |
Output is correct |
34 |
Correct |
277 ms |
21496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5120 KB |
Output is correct |
2 |
Correct |
6 ms |
5120 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
5 ms |
5120 KB |
Output is correct |
5 |
Correct |
6 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
6 ms |
5120 KB |
Output is correct |
8 |
Correct |
6 ms |
5120 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
7 ms |
5120 KB |
Output is correct |
11 |
Correct |
6 ms |
5120 KB |
Output is correct |
12 |
Correct |
6 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 |
5120 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
9 ms |
5120 KB |
Output is correct |
22 |
Correct |
12 ms |
10112 KB |
Output is correct |
23 |
Correct |
11 ms |
9472 KB |
Output is correct |
24 |
Correct |
12 ms |
10880 KB |
Output is correct |
25 |
Correct |
11 ms |
8704 KB |
Output is correct |
26 |
Correct |
9 ms |
7808 KB |
Output is correct |
27 |
Correct |
6 ms |
5120 KB |
Output is correct |
28 |
Correct |
8 ms |
6784 KB |
Output is correct |
29 |
Correct |
9 ms |
7680 KB |
Output is correct |
30 |
Correct |
10 ms |
7936 KB |
Output is correct |
31 |
Correct |
11 ms |
8704 KB |
Output is correct |
32 |
Correct |
10 ms |
8804 KB |
Output is correct |
33 |
Correct |
12 ms |
10496 KB |
Output is correct |
34 |
Correct |
12 ms |
9600 KB |
Output is correct |
35 |
Correct |
12 ms |
11008 KB |
Output is correct |
36 |
Correct |
12 ms |
11648 KB |
Output is correct |
37 |
Correct |
10 ms |
8960 KB |
Output is correct |
38 |
Correct |
9 ms |
7552 KB |
Output is correct |
39 |
Correct |
134 ms |
13244 KB |
Output is correct |
40 |
Correct |
138 ms |
13384 KB |
Output is correct |
41 |
Correct |
146 ms |
13296 KB |
Output is correct |
42 |
Correct |
131 ms |
13376 KB |
Output is correct |
43 |
Correct |
89 ms |
13560 KB |
Output is correct |
44 |
Correct |
81 ms |
13432 KB |
Output is correct |
45 |
Correct |
148 ms |
15224 KB |
Output is correct |
46 |
Correct |
93 ms |
17400 KB |
Output is correct |
47 |
Correct |
194 ms |
21760 KB |
Output is correct |
48 |
Correct |
365 ms |
30196 KB |
Output is correct |
49 |
Correct |
376 ms |
29388 KB |
Output is correct |
50 |
Correct |
217 ms |
22008 KB |
Output is correct |
51 |
Correct |
195 ms |
21752 KB |
Output is correct |
52 |
Correct |
233 ms |
21880 KB |
Output is correct |
53 |
Correct |
325 ms |
20728 KB |
Output is correct |
54 |
Correct |
277 ms |
21496 KB |
Output is correct |
55 |
Correct |
15 ms |
5888 KB |
Output is correct |
56 |
Correct |
17 ms |
5860 KB |
Output is correct |
57 |
Correct |
82 ms |
13404 KB |
Output is correct |
58 |
Correct |
41 ms |
13164 KB |
Output is correct |
59 |
Correct |
96 ms |
18168 KB |
Output is correct |
60 |
Correct |
612 ms |
34040 KB |
Output is correct |
61 |
Correct |
188 ms |
22008 KB |
Output is correct |
62 |
Correct |
215 ms |
21864 KB |
Output is correct |
63 |
Correct |
300 ms |
21900 KB |
Output is correct |
64 |
Correct |
593 ms |
24444 KB |
Output is correct |
65 |
Correct |
243 ms |
22660 KB |
Output is correct |
66 |
Correct |
623 ms |
35960 KB |
Output is correct |
67 |
Correct |
127 ms |
22500 KB |
Output is correct |
68 |
Correct |
315 ms |
27768 KB |
Output is correct |
69 |
Correct |
344 ms |
28276 KB |
Output is correct |
70 |
Correct |
308 ms |
27000 KB |
Output is correct |