# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
98067 |
2019-02-20T13:04:11 Z |
SpeedOfMagic |
Race (IOI11_race) |
C++17 |
|
3000 ms |
30668 KB |
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
template<typename T> using v = vector<T>;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
//code starts here
const int maxN = 2e5 + 1;
char vis[maxN];
int siz[maxN];
v<pair<int, int>> t[maxN];
int calcSiz(int cur, int p) {
siz[cur] = 1;
for (auto i : t[cur])
if (i.fs != p && !vis[cur])
siz[cur] += calcSiz(i.fs, cur);
return siz[cur];
}
const int maxK = 1e6 + 1;
pair<pair<int, int>, pair<int, int>> d[maxK];
int version[maxK];
int curVersion = 0;
int num;
int k;
vint added;
pair<pair<int, int>, pair<int, int>> init = {{maxN, -1}, {maxN, -1}};
void add(int cur, int curDist, int h, int p) {
if (curDist > k)
return;
if (curVersion != version[curDist]) {
d[curDist] = init;
version[curDist] = curVersion;
}
if (h < d[curDist].fs.fs) {
if (d[curDist].fs.sc == -1 && curDist <= k / 2)
added.pb(curDist);
if (d[curDist].fs.sc != num)
d[curDist].sc = d[curDist].fs;
d[curDist].fs = make_pair(h, num);
} else if (h < d[curDist].sc.fs && d[curDist].fs.sc != num)
d[curDist].sc = make_pair(h, num);
for (auto i : t[cur])
if (i.fs != p && !vis[i.fs])
add(i.fs, curDist + i.sc, h + 1, cur);
}
int ans = maxN + 5;
inline void find_centroid(int cur) {
int lim = calcSiz(cur, -1) / 2;
bool again = 1;
int pr = -1;
while (again) {
again = 0;
for (auto i : t[cur])
if (i.fs != pr && !vis[i.fs] && siz[i.fs] > lim) {
pr = cur;
cur = i.fs;
again = 1;
break;
}
}
added = vint();
vis[cur] = 1;
curVersion++;
num = 0;
added.pb(0);
d[0] = {{0, -2}, {maxN, -1}};
for (auto i : t[cur])
if (!vis[i.fs]) {
add(i.fs, i.sc, 1, cur);
num++;
}
for (int i : added) {
int o = k - i;
if (curVersion != version[o]) {
d[o] = init;
version[o] = curVersion;
}
if (d[i].fs.sc != d[o].fs.sc)
ans = min(ans, d[i].fs.fs + d[o].fs.fs);
else {
if (d[i].fs.sc != d[o].sc.sc)
ans = min(ans, d[i].fs.fs + d[o].sc.fs);
if (d[i].sc.sc != d[o].fs.sc)
ans = min(ans, d[i].sc.fs + d[o].fs.fs);
if (d[i].sc.sc != d[o].sc.sc)
ans = min(ans, d[i].sc.fs + d[o].sc.fs);
}
}
for (auto i : t[cur])
if (!vis[i.fs])
find_centroid(i.fs);
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
memset(vis, 0, sizeof vis);
memset(version, 0, sizeof version);
rep(i, 0, N - 1) {
t[H[i][0]].pb({H[i][1], L[i]});
t[H[i][1]].pb({H[i][0], L[i]});
}
find_centroid(0);
if (ans >= maxN)
return -1;
else
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
9088 KB |
Output is correct |
2 |
Correct |
12 ms |
9216 KB |
Output is correct |
3 |
Correct |
10 ms |
9088 KB |
Output is correct |
4 |
Correct |
10 ms |
9216 KB |
Output is correct |
5 |
Correct |
10 ms |
9216 KB |
Output is correct |
6 |
Correct |
10 ms |
9216 KB |
Output is correct |
7 |
Correct |
12 ms |
9216 KB |
Output is correct |
8 |
Correct |
11 ms |
9216 KB |
Output is correct |
9 |
Correct |
10 ms |
9276 KB |
Output is correct |
10 |
Correct |
11 ms |
9216 KB |
Output is correct |
11 |
Correct |
10 ms |
9216 KB |
Output is correct |
12 |
Correct |
10 ms |
9176 KB |
Output is correct |
13 |
Correct |
10 ms |
9132 KB |
Output is correct |
14 |
Correct |
10 ms |
9088 KB |
Output is correct |
15 |
Correct |
12 ms |
9088 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
13 ms |
9088 KB |
Output is correct |
18 |
Correct |
10 ms |
9216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
9088 KB |
Output is correct |
2 |
Correct |
12 ms |
9216 KB |
Output is correct |
3 |
Correct |
10 ms |
9088 KB |
Output is correct |
4 |
Correct |
10 ms |
9216 KB |
Output is correct |
5 |
Correct |
10 ms |
9216 KB |
Output is correct |
6 |
Correct |
10 ms |
9216 KB |
Output is correct |
7 |
Correct |
12 ms |
9216 KB |
Output is correct |
8 |
Correct |
11 ms |
9216 KB |
Output is correct |
9 |
Correct |
10 ms |
9276 KB |
Output is correct |
10 |
Correct |
11 ms |
9216 KB |
Output is correct |
11 |
Correct |
10 ms |
9216 KB |
Output is correct |
12 |
Correct |
10 ms |
9176 KB |
Output is correct |
13 |
Correct |
10 ms |
9132 KB |
Output is correct |
14 |
Correct |
10 ms |
9088 KB |
Output is correct |
15 |
Correct |
12 ms |
9088 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
13 ms |
9088 KB |
Output is correct |
18 |
Correct |
10 ms |
9216 KB |
Output is correct |
19 |
Correct |
9 ms |
9088 KB |
Output is correct |
20 |
Correct |
18 ms |
9112 KB |
Output is correct |
21 |
Correct |
11 ms |
9216 KB |
Output is correct |
22 |
Correct |
15 ms |
14336 KB |
Output is correct |
23 |
Correct |
15 ms |
13696 KB |
Output is correct |
24 |
Correct |
18 ms |
15488 KB |
Output is correct |
25 |
Correct |
18 ms |
19968 KB |
Output is correct |
26 |
Correct |
14 ms |
13184 KB |
Output is correct |
27 |
Correct |
12 ms |
9216 KB |
Output is correct |
28 |
Correct |
14 ms |
12288 KB |
Output is correct |
29 |
Correct |
16 ms |
14208 KB |
Output is correct |
30 |
Correct |
19 ms |
14976 KB |
Output is correct |
31 |
Correct |
16 ms |
18560 KB |
Output is correct |
32 |
Correct |
24 ms |
19328 KB |
Output is correct |
33 |
Correct |
23 ms |
20992 KB |
Output is correct |
34 |
Correct |
19 ms |
17480 KB |
Output is correct |
35 |
Correct |
20 ms |
19840 KB |
Output is correct |
36 |
Correct |
15 ms |
20736 KB |
Output is correct |
37 |
Correct |
18 ms |
18552 KB |
Output is correct |
38 |
Correct |
18 ms |
16256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
9088 KB |
Output is correct |
2 |
Correct |
12 ms |
9216 KB |
Output is correct |
3 |
Correct |
10 ms |
9088 KB |
Output is correct |
4 |
Correct |
10 ms |
9216 KB |
Output is correct |
5 |
Correct |
10 ms |
9216 KB |
Output is correct |
6 |
Correct |
10 ms |
9216 KB |
Output is correct |
7 |
Correct |
12 ms |
9216 KB |
Output is correct |
8 |
Correct |
11 ms |
9216 KB |
Output is correct |
9 |
Correct |
10 ms |
9276 KB |
Output is correct |
10 |
Correct |
11 ms |
9216 KB |
Output is correct |
11 |
Correct |
10 ms |
9216 KB |
Output is correct |
12 |
Correct |
10 ms |
9176 KB |
Output is correct |
13 |
Correct |
10 ms |
9132 KB |
Output is correct |
14 |
Correct |
10 ms |
9088 KB |
Output is correct |
15 |
Correct |
12 ms |
9088 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
13 ms |
9088 KB |
Output is correct |
18 |
Correct |
10 ms |
9216 KB |
Output is correct |
19 |
Correct |
172 ms |
15756 KB |
Output is correct |
20 |
Correct |
230 ms |
15736 KB |
Output is correct |
21 |
Correct |
214 ms |
15736 KB |
Output is correct |
22 |
Correct |
236 ms |
15864 KB |
Output is correct |
23 |
Correct |
168 ms |
16220 KB |
Output is correct |
24 |
Correct |
113 ms |
16020 KB |
Output is correct |
25 |
Correct |
214 ms |
17828 KB |
Output is correct |
26 |
Correct |
108 ms |
19832 KB |
Output is correct |
27 |
Correct |
418 ms |
22480 KB |
Output is correct |
28 |
Correct |
610 ms |
30668 KB |
Output is correct |
29 |
Correct |
547 ms |
30204 KB |
Output is correct |
30 |
Correct |
322 ms |
22688 KB |
Output is correct |
31 |
Correct |
363 ms |
23008 KB |
Output is correct |
32 |
Correct |
364 ms |
22780 KB |
Output is correct |
33 |
Correct |
466 ms |
21628 KB |
Output is correct |
34 |
Correct |
416 ms |
21496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
9088 KB |
Output is correct |
2 |
Correct |
12 ms |
9216 KB |
Output is correct |
3 |
Correct |
10 ms |
9088 KB |
Output is correct |
4 |
Correct |
10 ms |
9216 KB |
Output is correct |
5 |
Correct |
10 ms |
9216 KB |
Output is correct |
6 |
Correct |
10 ms |
9216 KB |
Output is correct |
7 |
Correct |
12 ms |
9216 KB |
Output is correct |
8 |
Correct |
11 ms |
9216 KB |
Output is correct |
9 |
Correct |
10 ms |
9276 KB |
Output is correct |
10 |
Correct |
11 ms |
9216 KB |
Output is correct |
11 |
Correct |
10 ms |
9216 KB |
Output is correct |
12 |
Correct |
10 ms |
9176 KB |
Output is correct |
13 |
Correct |
10 ms |
9132 KB |
Output is correct |
14 |
Correct |
10 ms |
9088 KB |
Output is correct |
15 |
Correct |
12 ms |
9088 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
13 ms |
9088 KB |
Output is correct |
18 |
Correct |
10 ms |
9216 KB |
Output is correct |
19 |
Correct |
9 ms |
9088 KB |
Output is correct |
20 |
Correct |
18 ms |
9112 KB |
Output is correct |
21 |
Correct |
11 ms |
9216 KB |
Output is correct |
22 |
Correct |
15 ms |
14336 KB |
Output is correct |
23 |
Correct |
15 ms |
13696 KB |
Output is correct |
24 |
Correct |
18 ms |
15488 KB |
Output is correct |
25 |
Correct |
18 ms |
19968 KB |
Output is correct |
26 |
Correct |
14 ms |
13184 KB |
Output is correct |
27 |
Correct |
12 ms |
9216 KB |
Output is correct |
28 |
Correct |
14 ms |
12288 KB |
Output is correct |
29 |
Correct |
16 ms |
14208 KB |
Output is correct |
30 |
Correct |
19 ms |
14976 KB |
Output is correct |
31 |
Correct |
16 ms |
18560 KB |
Output is correct |
32 |
Correct |
24 ms |
19328 KB |
Output is correct |
33 |
Correct |
23 ms |
20992 KB |
Output is correct |
34 |
Correct |
19 ms |
17480 KB |
Output is correct |
35 |
Correct |
20 ms |
19840 KB |
Output is correct |
36 |
Correct |
15 ms |
20736 KB |
Output is correct |
37 |
Correct |
18 ms |
18552 KB |
Output is correct |
38 |
Correct |
18 ms |
16256 KB |
Output is correct |
39 |
Correct |
172 ms |
15756 KB |
Output is correct |
40 |
Correct |
230 ms |
15736 KB |
Output is correct |
41 |
Correct |
214 ms |
15736 KB |
Output is correct |
42 |
Correct |
236 ms |
15864 KB |
Output is correct |
43 |
Correct |
168 ms |
16220 KB |
Output is correct |
44 |
Correct |
113 ms |
16020 KB |
Output is correct |
45 |
Correct |
214 ms |
17828 KB |
Output is correct |
46 |
Correct |
108 ms |
19832 KB |
Output is correct |
47 |
Correct |
418 ms |
22480 KB |
Output is correct |
48 |
Correct |
610 ms |
30668 KB |
Output is correct |
49 |
Correct |
547 ms |
30204 KB |
Output is correct |
50 |
Correct |
322 ms |
22688 KB |
Output is correct |
51 |
Correct |
363 ms |
23008 KB |
Output is correct |
52 |
Correct |
364 ms |
22780 KB |
Output is correct |
53 |
Correct |
466 ms |
21628 KB |
Output is correct |
54 |
Correct |
416 ms |
21496 KB |
Output is correct |
55 |
Correct |
20 ms |
9840 KB |
Output is correct |
56 |
Correct |
28 ms |
9848 KB |
Output is correct |
57 |
Correct |
113 ms |
15932 KB |
Output is correct |
58 |
Execution timed out |
3008 ms |
15724 KB |
Time limit exceeded |
59 |
Halted |
0 ms |
0 KB |
- |