| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 654503 |
2022-10-31T14:00:43 Z |
adaawf |
Race (IOI11_race) |
C++14 |
|
1472 ms |
75248 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> g[300005], a;
int n, k, c[300005], dd[300005], res = 999999999;
int dfs(int x, int p) {
c[x] = 1;
for (auto w : g[x]) {
if (w[0] != p && dd[w[0]] == 0) {
c[x] += dfs(w[0], x);
}
}
return c[x];
}
void dfs2(int x, int p, int v, int num, int d) {
for (auto w : g[x]) {
if (w[0] != p && dd[w[0]] == 0) {
dfs2(w[0], x, v + w[1], num + 1, d);
}
}
a.push_back({v, num, d});
}
int centroid(int x, int sz, int p) {
for (auto w : g[x]) {
if (w[0] != p && dd[w[0]] == 0 && c[w[0]] * 2 > sz) {
return centroid(w[0], sz, x);
}
}
return x;
}
void trya(int x, int p) {
int c = centroid(x, dfs(x, -1), -1), d = 0;
a.clear();
for (auto w : g[c]) {
if (dd[w[0]] == 0) {
dfs2(w[0], c, w[1], 1, d);
}
a.push_back({0, 0, d});
d++;
}
sort(a.begin(), a.end());
int l = 0, r = a.size() - 1;
while (l <= r) {
if (a[l][0] + a[r][0] > k) {
r--;
}
else if (a[l][0] + a[r][0] == k) {
if (a[l][2] == a[r][2]) {
if (a[r][0] != a[r - 1][0]) {
l++;
continue;
}
r--;
continue;
}
else {
res = min(res, a[l][1] + a[r][1]);
r--;
}
}
else if (a[l][0] + a[r][0] < k) {
l++;
}
}
dd[c] = 1;
for (auto w : g[c]) {
if (dd[w[0]] == 0) {
trya(w[0], c);
}
}
}
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]});
}
trya(0, -1);
if (res == 999999999) return -1;
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7352 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7412 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7352 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7412 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7352 KB |
Output is correct |
| 21 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 22 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 23 |
Correct |
8 ms |
7508 KB |
Output is correct |
| 24 |
Correct |
6 ms |
7500 KB |
Output is correct |
| 25 |
Correct |
6 ms |
7496 KB |
Output is correct |
| 26 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 27 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 28 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 29 |
Correct |
6 ms |
7492 KB |
Output is correct |
| 30 |
Correct |
7 ms |
7496 KB |
Output is correct |
| 31 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 32 |
Correct |
6 ms |
7496 KB |
Output is correct |
| 33 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 34 |
Correct |
8 ms |
7500 KB |
Output is correct |
| 35 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 36 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 37 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 38 |
Correct |
6 ms |
7508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7352 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7412 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 19 |
Correct |
590 ms |
28904 KB |
Output is correct |
| 20 |
Correct |
605 ms |
28844 KB |
Output is correct |
| 21 |
Correct |
549 ms |
28948 KB |
Output is correct |
| 22 |
Correct |
535 ms |
28900 KB |
Output is correct |
| 23 |
Correct |
530 ms |
29432 KB |
Output is correct |
| 24 |
Correct |
286 ms |
27956 KB |
Output is correct |
| 25 |
Correct |
514 ms |
37152 KB |
Output is correct |
| 26 |
Correct |
459 ms |
41156 KB |
Output is correct |
| 27 |
Correct |
584 ms |
50472 KB |
Output is correct |
| 28 |
Correct |
1392 ms |
75248 KB |
Output is correct |
| 29 |
Correct |
1363 ms |
73728 KB |
Output is correct |
| 30 |
Correct |
646 ms |
50640 KB |
Output is correct |
| 31 |
Correct |
621 ms |
50532 KB |
Output is correct |
| 32 |
Correct |
740 ms |
50636 KB |
Output is correct |
| 33 |
Correct |
999 ms |
50260 KB |
Output is correct |
| 34 |
Correct |
1002 ms |
51084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7352 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7412 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7352 KB |
Output is correct |
| 21 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 22 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 23 |
Correct |
8 ms |
7508 KB |
Output is correct |
| 24 |
Correct |
6 ms |
7500 KB |
Output is correct |
| 25 |
Correct |
6 ms |
7496 KB |
Output is correct |
| 26 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 27 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 28 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 29 |
Correct |
6 ms |
7492 KB |
Output is correct |
| 30 |
Correct |
7 ms |
7496 KB |
Output is correct |
| 31 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 32 |
Correct |
6 ms |
7496 KB |
Output is correct |
| 33 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 34 |
Correct |
8 ms |
7500 KB |
Output is correct |
| 35 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 36 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 37 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 38 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 39 |
Correct |
590 ms |
28904 KB |
Output is correct |
| 40 |
Correct |
605 ms |
28844 KB |
Output is correct |
| 41 |
Correct |
549 ms |
28948 KB |
Output is correct |
| 42 |
Correct |
535 ms |
28900 KB |
Output is correct |
| 43 |
Correct |
530 ms |
29432 KB |
Output is correct |
| 44 |
Correct |
286 ms |
27956 KB |
Output is correct |
| 45 |
Correct |
514 ms |
37152 KB |
Output is correct |
| 46 |
Correct |
459 ms |
41156 KB |
Output is correct |
| 47 |
Correct |
584 ms |
50472 KB |
Output is correct |
| 48 |
Correct |
1392 ms |
75248 KB |
Output is correct |
| 49 |
Correct |
1363 ms |
73728 KB |
Output is correct |
| 50 |
Correct |
646 ms |
50640 KB |
Output is correct |
| 51 |
Correct |
621 ms |
50532 KB |
Output is correct |
| 52 |
Correct |
740 ms |
50636 KB |
Output is correct |
| 53 |
Correct |
999 ms |
50260 KB |
Output is correct |
| 54 |
Correct |
1002 ms |
51084 KB |
Output is correct |
| 55 |
Correct |
32 ms |
9556 KB |
Output is correct |
| 56 |
Correct |
36 ms |
9556 KB |
Output is correct |
| 57 |
Correct |
457 ms |
29488 KB |
Output is correct |
| 58 |
Correct |
116 ms |
33032 KB |
Output is correct |
| 59 |
Correct |
479 ms |
41124 KB |
Output is correct |
| 60 |
Correct |
1389 ms |
74120 KB |
Output is correct |
| 61 |
Correct |
612 ms |
50668 KB |
Output is correct |
| 62 |
Correct |
636 ms |
50540 KB |
Output is correct |
| 63 |
Correct |
759 ms |
50528 KB |
Output is correct |
| 64 |
Correct |
1421 ms |
51188 KB |
Output is correct |
| 65 |
Correct |
1141 ms |
51800 KB |
Output is correct |
| 66 |
Correct |
1472 ms |
70180 KB |
Output is correct |
| 67 |
Correct |
419 ms |
59924 KB |
Output is correct |
| 68 |
Correct |
735 ms |
50052 KB |
Output is correct |
| 69 |
Correct |
760 ms |
50416 KB |
Output is correct |
| 70 |
Correct |
710 ms |
48308 KB |
Output is correct |
