#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[i.fs])
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;
int added[maxN];
int ptr = 0;
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[ptr++] = 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;
}
}
ptr = 0;
vis[cur] = 1;
curVersion++;
num = 0;
added[ptr++] = 0;
d[0] = {{0, -2}, {maxN, -1}};
for (auto i : t[cur])
if (!vis[i.fs]) {
add(i.fs, i.sc, 1, cur);
num++;
}
rep(z, 0, ptr) {
int i = added[z];
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9216 KB |
Output is correct |
2 |
Correct |
12 ms |
9216 KB |
Output is correct |
3 |
Correct |
11 ms |
9088 KB |
Output is correct |
4 |
Correct |
12 ms |
9216 KB |
Output is correct |
5 |
Correct |
10 ms |
9216 KB |
Output is correct |
6 |
Correct |
12 ms |
9216 KB |
Output is correct |
7 |
Correct |
8 ms |
9216 KB |
Output is correct |
8 |
Correct |
12 ms |
9216 KB |
Output is correct |
9 |
Correct |
11 ms |
9216 KB |
Output is correct |
10 |
Correct |
11 ms |
9216 KB |
Output is correct |
11 |
Correct |
11 ms |
9216 KB |
Output is correct |
12 |
Correct |
10 ms |
9216 KB |
Output is correct |
13 |
Correct |
11 ms |
9088 KB |
Output is correct |
14 |
Correct |
11 ms |
9088 KB |
Output is correct |
15 |
Correct |
11 ms |
9188 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
10 ms |
9088 KB |
Output is correct |
18 |
Correct |
11 ms |
9216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9216 KB |
Output is correct |
2 |
Correct |
12 ms |
9216 KB |
Output is correct |
3 |
Correct |
11 ms |
9088 KB |
Output is correct |
4 |
Correct |
12 ms |
9216 KB |
Output is correct |
5 |
Correct |
10 ms |
9216 KB |
Output is correct |
6 |
Correct |
12 ms |
9216 KB |
Output is correct |
7 |
Correct |
8 ms |
9216 KB |
Output is correct |
8 |
Correct |
12 ms |
9216 KB |
Output is correct |
9 |
Correct |
11 ms |
9216 KB |
Output is correct |
10 |
Correct |
11 ms |
9216 KB |
Output is correct |
11 |
Correct |
11 ms |
9216 KB |
Output is correct |
12 |
Correct |
10 ms |
9216 KB |
Output is correct |
13 |
Correct |
11 ms |
9088 KB |
Output is correct |
14 |
Correct |
11 ms |
9088 KB |
Output is correct |
15 |
Correct |
11 ms |
9188 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
10 ms |
9088 KB |
Output is correct |
18 |
Correct |
11 ms |
9216 KB |
Output is correct |
19 |
Correct |
12 ms |
9216 KB |
Output is correct |
20 |
Correct |
10 ms |
9120 KB |
Output is correct |
21 |
Correct |
12 ms |
9216 KB |
Output is correct |
22 |
Correct |
15 ms |
14328 KB |
Output is correct |
23 |
Correct |
15 ms |
13568 KB |
Output is correct |
24 |
Correct |
20 ms |
15616 KB |
Output is correct |
25 |
Correct |
23 ms |
19968 KB |
Output is correct |
26 |
Correct |
14 ms |
13056 KB |
Output is correct |
27 |
Correct |
12 ms |
9216 KB |
Output is correct |
28 |
Correct |
16 ms |
12288 KB |
Output is correct |
29 |
Correct |
18 ms |
14208 KB |
Output is correct |
30 |
Correct |
16 ms |
14976 KB |
Output is correct |
31 |
Correct |
22 ms |
18556 KB |
Output is correct |
32 |
Correct |
21 ms |
19328 KB |
Output is correct |
33 |
Correct |
21 ms |
20864 KB |
Output is correct |
34 |
Correct |
22 ms |
17532 KB |
Output is correct |
35 |
Correct |
18 ms |
19712 KB |
Output is correct |
36 |
Correct |
20 ms |
20608 KB |
Output is correct |
37 |
Correct |
12 ms |
18560 KB |
Output is correct |
38 |
Correct |
16 ms |
16256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9216 KB |
Output is correct |
2 |
Correct |
12 ms |
9216 KB |
Output is correct |
3 |
Correct |
11 ms |
9088 KB |
Output is correct |
4 |
Correct |
12 ms |
9216 KB |
Output is correct |
5 |
Correct |
10 ms |
9216 KB |
Output is correct |
6 |
Correct |
12 ms |
9216 KB |
Output is correct |
7 |
Correct |
8 ms |
9216 KB |
Output is correct |
8 |
Correct |
12 ms |
9216 KB |
Output is correct |
9 |
Correct |
11 ms |
9216 KB |
Output is correct |
10 |
Correct |
11 ms |
9216 KB |
Output is correct |
11 |
Correct |
11 ms |
9216 KB |
Output is correct |
12 |
Correct |
10 ms |
9216 KB |
Output is correct |
13 |
Correct |
11 ms |
9088 KB |
Output is correct |
14 |
Correct |
11 ms |
9088 KB |
Output is correct |
15 |
Correct |
11 ms |
9188 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
10 ms |
9088 KB |
Output is correct |
18 |
Correct |
11 ms |
9216 KB |
Output is correct |
19 |
Correct |
230 ms |
14712 KB |
Output is correct |
20 |
Correct |
215 ms |
14716 KB |
Output is correct |
21 |
Correct |
182 ms |
14712 KB |
Output is correct |
22 |
Correct |
272 ms |
14712 KB |
Output is correct |
23 |
Correct |
148 ms |
14840 KB |
Output is correct |
24 |
Correct |
126 ms |
14840 KB |
Output is correct |
25 |
Correct |
196 ms |
16644 KB |
Output is correct |
26 |
Correct |
94 ms |
18808 KB |
Output is correct |
27 |
Correct |
259 ms |
20196 KB |
Output is correct |
28 |
Correct |
554 ms |
28280 KB |
Output is correct |
29 |
Correct |
534 ms |
27640 KB |
Output is correct |
30 |
Correct |
255 ms |
20088 KB |
Output is correct |
31 |
Correct |
316 ms |
20124 KB |
Output is correct |
32 |
Correct |
345 ms |
20088 KB |
Output is correct |
33 |
Correct |
459 ms |
19024 KB |
Output is correct |
34 |
Correct |
431 ms |
19064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9216 KB |
Output is correct |
2 |
Correct |
12 ms |
9216 KB |
Output is correct |
3 |
Correct |
11 ms |
9088 KB |
Output is correct |
4 |
Correct |
12 ms |
9216 KB |
Output is correct |
5 |
Correct |
10 ms |
9216 KB |
Output is correct |
6 |
Correct |
12 ms |
9216 KB |
Output is correct |
7 |
Correct |
8 ms |
9216 KB |
Output is correct |
8 |
Correct |
12 ms |
9216 KB |
Output is correct |
9 |
Correct |
11 ms |
9216 KB |
Output is correct |
10 |
Correct |
11 ms |
9216 KB |
Output is correct |
11 |
Correct |
11 ms |
9216 KB |
Output is correct |
12 |
Correct |
10 ms |
9216 KB |
Output is correct |
13 |
Correct |
11 ms |
9088 KB |
Output is correct |
14 |
Correct |
11 ms |
9088 KB |
Output is correct |
15 |
Correct |
11 ms |
9188 KB |
Output is correct |
16 |
Correct |
10 ms |
9088 KB |
Output is correct |
17 |
Correct |
10 ms |
9088 KB |
Output is correct |
18 |
Correct |
11 ms |
9216 KB |
Output is correct |
19 |
Correct |
12 ms |
9216 KB |
Output is correct |
20 |
Correct |
10 ms |
9120 KB |
Output is correct |
21 |
Correct |
12 ms |
9216 KB |
Output is correct |
22 |
Correct |
15 ms |
14328 KB |
Output is correct |
23 |
Correct |
15 ms |
13568 KB |
Output is correct |
24 |
Correct |
20 ms |
15616 KB |
Output is correct |
25 |
Correct |
23 ms |
19968 KB |
Output is correct |
26 |
Correct |
14 ms |
13056 KB |
Output is correct |
27 |
Correct |
12 ms |
9216 KB |
Output is correct |
28 |
Correct |
16 ms |
12288 KB |
Output is correct |
29 |
Correct |
18 ms |
14208 KB |
Output is correct |
30 |
Correct |
16 ms |
14976 KB |
Output is correct |
31 |
Correct |
22 ms |
18556 KB |
Output is correct |
32 |
Correct |
21 ms |
19328 KB |
Output is correct |
33 |
Correct |
21 ms |
20864 KB |
Output is correct |
34 |
Correct |
22 ms |
17532 KB |
Output is correct |
35 |
Correct |
18 ms |
19712 KB |
Output is correct |
36 |
Correct |
20 ms |
20608 KB |
Output is correct |
37 |
Correct |
12 ms |
18560 KB |
Output is correct |
38 |
Correct |
16 ms |
16256 KB |
Output is correct |
39 |
Correct |
230 ms |
14712 KB |
Output is correct |
40 |
Correct |
215 ms |
14716 KB |
Output is correct |
41 |
Correct |
182 ms |
14712 KB |
Output is correct |
42 |
Correct |
272 ms |
14712 KB |
Output is correct |
43 |
Correct |
148 ms |
14840 KB |
Output is correct |
44 |
Correct |
126 ms |
14840 KB |
Output is correct |
45 |
Correct |
196 ms |
16644 KB |
Output is correct |
46 |
Correct |
94 ms |
18808 KB |
Output is correct |
47 |
Correct |
259 ms |
20196 KB |
Output is correct |
48 |
Correct |
554 ms |
28280 KB |
Output is correct |
49 |
Correct |
534 ms |
27640 KB |
Output is correct |
50 |
Correct |
255 ms |
20088 KB |
Output is correct |
51 |
Correct |
316 ms |
20124 KB |
Output is correct |
52 |
Correct |
345 ms |
20088 KB |
Output is correct |
53 |
Correct |
459 ms |
19024 KB |
Output is correct |
54 |
Correct |
431 ms |
19064 KB |
Output is correct |
55 |
Correct |
21 ms |
9932 KB |
Output is correct |
56 |
Correct |
21 ms |
9840 KB |
Output is correct |
57 |
Correct |
87 ms |
14840 KB |
Output is correct |
58 |
Correct |
61 ms |
14956 KB |
Output is correct |
59 |
Correct |
114 ms |
23144 KB |
Output is correct |
60 |
Correct |
872 ms |
46692 KB |
Output is correct |
61 |
Correct |
272 ms |
23008 KB |
Output is correct |
62 |
Correct |
347 ms |
23164 KB |
Output is correct |
63 |
Correct |
442 ms |
23004 KB |
Output is correct |
64 |
Correct |
875 ms |
31268 KB |
Output is correct |
65 |
Correct |
503 ms |
23032 KB |
Output is correct |
66 |
Correct |
916 ms |
44560 KB |
Output is correct |
67 |
Correct |
203 ms |
23336 KB |
Output is correct |
68 |
Correct |
525 ms |
33784 KB |
Output is correct |
69 |
Correct |
480 ms |
34296 KB |
Output is correct |
70 |
Correct |
463 ms |
33244 KB |
Output is correct |