# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
62162 |
2018-07-27T15:56:36 Z |
reality |
Race (IOI11_race) |
C++17 |
|
1752 ms |
67624 KB |
#include "race.h"
# include <bits/stdc++.h>
using namespace std;
# define x first
# define y second
# define ll long long
# define vi vector < int >
# define vl vector < ll >
# define pii pair < int , int >
# define mp make_pair
# define vii vector < pii >
# define pb push_back
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int best_path(int N, int K, int H[][2], int L[])
{
static vii g[1 << 20];
int n = N;
for (int i = 0;i < n - 1;++i)
g[H[i][0] + 1].pb(mp(H[i][1] + 1,L[i])),
g[H[i][1] + 1].pb(mp(H[i][0] + 1,L[i]));
int ans = 1e9;
static int S[1 << 20];
static int was[1 << 20];
static int vv[1 << 20];
static int D[1 << 20];
for (int i = 1;i <= n;++i)
was[i] = 1;
for (int i = 1;i <= 1e6 + 5;++i)
D[i] = -1;
vi us;
function < void(int,int) > dfs1 = [&](int node,int prev)
{
vv[node] = 0;
us.pb(node);
S[node] = 1;
for (auto it : g[node])
if (vv[it.x] && was[it.x])
dfs1(it.x,node),S[node] += S[it.x];
};
vi vis;
function < void(int,int,int,int) > dfs2 = [&](int node,int prev,int sum,int dep)
{
if (sum > K)
return;
vis.pb(sum);
if (D[K - sum] != -1)
smin(ans,D[K - sum] + dep);
for (auto it : g[node])
if (it.x != prev && was[it.x])
dfs2(it.x,node,sum + it.y,dep + 1);
};
function < void(int,int,int,int) > dfs3 = [&](int node,int prev,int sum,int dep)
{
if (sum > K)
return;
if (D[sum] == -1 || D[sum] > dep)
D[sum] = dep;
for (auto it : g[node])
if (it.x != prev && was[it.x])
dfs3(it.x,node,sum + it.y,dep + 1);
};
while (*max_element(was + 1,was + 1 + n))
{
for (int i = 1;i <= n;++i)
vv[i] = 1;
for (int i = 1;i <= n;++i)
if (vv[i] && was[i])
{
vis.clear();
us.clear();
dfs1(i,0);
const int sz = us.size();
pii mx = mp(n + 5,0);
for (auto vertex : us)
{
int mm = 0;
for (auto it : g[vertex])
if (was[it.x] && S[it.x] < S[vertex])
smax(mm,S[it.x]);
smax(mm,sz - S[vertex]);
smin(mx,mp(mm,vertex));
}
int vertex = mx.y;
for (auto it : g[vertex])
if (was[it.x])
{
dfs2(it.x,vertex,it.y,1);
dfs3(it.x,vertex,it.y,1);
}
was[vertex] = 0;
for (auto it : vis)
D[it] = -1;
}
}
if (ans == 1e9)
ans = -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
28924 KB |
Output is correct |
2 |
Correct |
31 ms |
28924 KB |
Output is correct |
3 |
Correct |
30 ms |
29104 KB |
Output is correct |
4 |
Correct |
31 ms |
29104 KB |
Output is correct |
5 |
Correct |
31 ms |
29104 KB |
Output is correct |
6 |
Correct |
31 ms |
29140 KB |
Output is correct |
7 |
Correct |
33 ms |
29140 KB |
Output is correct |
8 |
Correct |
40 ms |
29140 KB |
Output is correct |
9 |
Correct |
34 ms |
29140 KB |
Output is correct |
10 |
Correct |
35 ms |
29140 KB |
Output is correct |
11 |
Correct |
37 ms |
29140 KB |
Output is correct |
12 |
Correct |
37 ms |
29140 KB |
Output is correct |
13 |
Correct |
35 ms |
29296 KB |
Output is correct |
14 |
Correct |
33 ms |
29296 KB |
Output is correct |
15 |
Correct |
38 ms |
29296 KB |
Output is correct |
16 |
Correct |
38 ms |
29296 KB |
Output is correct |
17 |
Correct |
35 ms |
29296 KB |
Output is correct |
18 |
Correct |
37 ms |
29296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
28924 KB |
Output is correct |
2 |
Correct |
31 ms |
28924 KB |
Output is correct |
3 |
Correct |
30 ms |
29104 KB |
Output is correct |
4 |
Correct |
31 ms |
29104 KB |
Output is correct |
5 |
Correct |
31 ms |
29104 KB |
Output is correct |
6 |
Correct |
31 ms |
29140 KB |
Output is correct |
7 |
Correct |
33 ms |
29140 KB |
Output is correct |
8 |
Correct |
40 ms |
29140 KB |
Output is correct |
9 |
Correct |
34 ms |
29140 KB |
Output is correct |
10 |
Correct |
35 ms |
29140 KB |
Output is correct |
11 |
Correct |
37 ms |
29140 KB |
Output is correct |
12 |
Correct |
37 ms |
29140 KB |
Output is correct |
13 |
Correct |
35 ms |
29296 KB |
Output is correct |
14 |
Correct |
33 ms |
29296 KB |
Output is correct |
15 |
Correct |
38 ms |
29296 KB |
Output is correct |
16 |
Correct |
38 ms |
29296 KB |
Output is correct |
17 |
Correct |
35 ms |
29296 KB |
Output is correct |
18 |
Correct |
37 ms |
29296 KB |
Output is correct |
19 |
Correct |
36 ms |
29296 KB |
Output is correct |
20 |
Correct |
40 ms |
29296 KB |
Output is correct |
21 |
Correct |
38 ms |
29296 KB |
Output is correct |
22 |
Correct |
31 ms |
29296 KB |
Output is correct |
23 |
Correct |
34 ms |
29296 KB |
Output is correct |
24 |
Correct |
34 ms |
29296 KB |
Output is correct |
25 |
Correct |
35 ms |
29296 KB |
Output is correct |
26 |
Correct |
36 ms |
29296 KB |
Output is correct |
27 |
Correct |
36 ms |
29296 KB |
Output is correct |
28 |
Correct |
36 ms |
29296 KB |
Output is correct |
29 |
Correct |
33 ms |
29296 KB |
Output is correct |
30 |
Correct |
35 ms |
29296 KB |
Output is correct |
31 |
Correct |
36 ms |
29296 KB |
Output is correct |
32 |
Correct |
37 ms |
29296 KB |
Output is correct |
33 |
Correct |
32 ms |
29296 KB |
Output is correct |
34 |
Correct |
33 ms |
29296 KB |
Output is correct |
35 |
Correct |
33 ms |
29296 KB |
Output is correct |
36 |
Correct |
32 ms |
29296 KB |
Output is correct |
37 |
Correct |
32 ms |
29296 KB |
Output is correct |
38 |
Correct |
34 ms |
29296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
28924 KB |
Output is correct |
2 |
Correct |
31 ms |
28924 KB |
Output is correct |
3 |
Correct |
30 ms |
29104 KB |
Output is correct |
4 |
Correct |
31 ms |
29104 KB |
Output is correct |
5 |
Correct |
31 ms |
29104 KB |
Output is correct |
6 |
Correct |
31 ms |
29140 KB |
Output is correct |
7 |
Correct |
33 ms |
29140 KB |
Output is correct |
8 |
Correct |
40 ms |
29140 KB |
Output is correct |
9 |
Correct |
34 ms |
29140 KB |
Output is correct |
10 |
Correct |
35 ms |
29140 KB |
Output is correct |
11 |
Correct |
37 ms |
29140 KB |
Output is correct |
12 |
Correct |
37 ms |
29140 KB |
Output is correct |
13 |
Correct |
35 ms |
29296 KB |
Output is correct |
14 |
Correct |
33 ms |
29296 KB |
Output is correct |
15 |
Correct |
38 ms |
29296 KB |
Output is correct |
16 |
Correct |
38 ms |
29296 KB |
Output is correct |
17 |
Correct |
35 ms |
29296 KB |
Output is correct |
18 |
Correct |
37 ms |
29296 KB |
Output is correct |
19 |
Correct |
493 ms |
35820 KB |
Output is correct |
20 |
Correct |
546 ms |
35820 KB |
Output is correct |
21 |
Correct |
550 ms |
35940 KB |
Output is correct |
22 |
Correct |
569 ms |
36452 KB |
Output is correct |
23 |
Correct |
469 ms |
36452 KB |
Output is correct |
24 |
Correct |
256 ms |
36452 KB |
Output is correct |
25 |
Correct |
606 ms |
39192 KB |
Output is correct |
26 |
Correct |
211 ms |
43628 KB |
Output is correct |
27 |
Correct |
478 ms |
43628 KB |
Output is correct |
28 |
Correct |
1200 ms |
59744 KB |
Output is correct |
29 |
Correct |
1227 ms |
61680 KB |
Output is correct |
30 |
Correct |
440 ms |
61680 KB |
Output is correct |
31 |
Correct |
516 ms |
61680 KB |
Output is correct |
32 |
Correct |
706 ms |
61680 KB |
Output is correct |
33 |
Correct |
1097 ms |
61680 KB |
Output is correct |
34 |
Correct |
971 ms |
61680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
28924 KB |
Output is correct |
2 |
Correct |
31 ms |
28924 KB |
Output is correct |
3 |
Correct |
30 ms |
29104 KB |
Output is correct |
4 |
Correct |
31 ms |
29104 KB |
Output is correct |
5 |
Correct |
31 ms |
29104 KB |
Output is correct |
6 |
Correct |
31 ms |
29140 KB |
Output is correct |
7 |
Correct |
33 ms |
29140 KB |
Output is correct |
8 |
Correct |
40 ms |
29140 KB |
Output is correct |
9 |
Correct |
34 ms |
29140 KB |
Output is correct |
10 |
Correct |
35 ms |
29140 KB |
Output is correct |
11 |
Correct |
37 ms |
29140 KB |
Output is correct |
12 |
Correct |
37 ms |
29140 KB |
Output is correct |
13 |
Correct |
35 ms |
29296 KB |
Output is correct |
14 |
Correct |
33 ms |
29296 KB |
Output is correct |
15 |
Correct |
38 ms |
29296 KB |
Output is correct |
16 |
Correct |
38 ms |
29296 KB |
Output is correct |
17 |
Correct |
35 ms |
29296 KB |
Output is correct |
18 |
Correct |
37 ms |
29296 KB |
Output is correct |
19 |
Correct |
36 ms |
29296 KB |
Output is correct |
20 |
Correct |
40 ms |
29296 KB |
Output is correct |
21 |
Correct |
38 ms |
29296 KB |
Output is correct |
22 |
Correct |
31 ms |
29296 KB |
Output is correct |
23 |
Correct |
34 ms |
29296 KB |
Output is correct |
24 |
Correct |
34 ms |
29296 KB |
Output is correct |
25 |
Correct |
35 ms |
29296 KB |
Output is correct |
26 |
Correct |
36 ms |
29296 KB |
Output is correct |
27 |
Correct |
36 ms |
29296 KB |
Output is correct |
28 |
Correct |
36 ms |
29296 KB |
Output is correct |
29 |
Correct |
33 ms |
29296 KB |
Output is correct |
30 |
Correct |
35 ms |
29296 KB |
Output is correct |
31 |
Correct |
36 ms |
29296 KB |
Output is correct |
32 |
Correct |
37 ms |
29296 KB |
Output is correct |
33 |
Correct |
32 ms |
29296 KB |
Output is correct |
34 |
Correct |
33 ms |
29296 KB |
Output is correct |
35 |
Correct |
33 ms |
29296 KB |
Output is correct |
36 |
Correct |
32 ms |
29296 KB |
Output is correct |
37 |
Correct |
32 ms |
29296 KB |
Output is correct |
38 |
Correct |
34 ms |
29296 KB |
Output is correct |
39 |
Correct |
493 ms |
35820 KB |
Output is correct |
40 |
Correct |
546 ms |
35820 KB |
Output is correct |
41 |
Correct |
550 ms |
35940 KB |
Output is correct |
42 |
Correct |
569 ms |
36452 KB |
Output is correct |
43 |
Correct |
469 ms |
36452 KB |
Output is correct |
44 |
Correct |
256 ms |
36452 KB |
Output is correct |
45 |
Correct |
606 ms |
39192 KB |
Output is correct |
46 |
Correct |
211 ms |
43628 KB |
Output is correct |
47 |
Correct |
478 ms |
43628 KB |
Output is correct |
48 |
Correct |
1200 ms |
59744 KB |
Output is correct |
49 |
Correct |
1227 ms |
61680 KB |
Output is correct |
50 |
Correct |
440 ms |
61680 KB |
Output is correct |
51 |
Correct |
516 ms |
61680 KB |
Output is correct |
52 |
Correct |
706 ms |
61680 KB |
Output is correct |
53 |
Correct |
1097 ms |
61680 KB |
Output is correct |
54 |
Correct |
971 ms |
61680 KB |
Output is correct |
55 |
Correct |
48 ms |
61680 KB |
Output is correct |
56 |
Correct |
47 ms |
61680 KB |
Output is correct |
57 |
Correct |
352 ms |
61680 KB |
Output is correct |
58 |
Correct |
129 ms |
61680 KB |
Output is correct |
59 |
Correct |
193 ms |
61680 KB |
Output is correct |
60 |
Correct |
1649 ms |
67624 KB |
Output is correct |
61 |
Correct |
529 ms |
67624 KB |
Output is correct |
62 |
Correct |
627 ms |
67624 KB |
Output is correct |
63 |
Correct |
942 ms |
67624 KB |
Output is correct |
64 |
Correct |
1752 ms |
67624 KB |
Output is correct |
65 |
Correct |
956 ms |
67624 KB |
Output is correct |
66 |
Correct |
1635 ms |
67624 KB |
Output is correct |
67 |
Correct |
368 ms |
67624 KB |
Output is correct |
68 |
Correct |
923 ms |
67624 KB |
Output is correct |
69 |
Correct |
919 ms |
67624 KB |
Output is correct |
70 |
Correct |
842 ms |
67624 KB |
Output is correct |