# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
99478 |
2019-03-04T10:22:34 Z |
naoai |
Race (IOI11_race) |
C++14 |
|
652 ms |
69884 KB |
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");
typedef long long i64;
const int nmax = 2e5;
static i64 K;
static int ans;
static int lant[nmax + 1], sz[nmax + 1];
static i64 ct[nmax + 1];
static vector<pair<int, int>> g[nmax + 1];
static set<pair<i64, int>> s[nmax + 1];
void dfs (int nod, int h, int dad = -1) {
sz[nod] = 1;
int mxf = -1, mxg = -1, valm = 0;
for (auto i : g[nod]) {
if (i.first != dad) {
dfs(i.first, h + 1, nod);
sz[nod] += sz[i.first];
if (sz[i.first] > mxg) {
mxg = sz[i.first];
mxf = i.first;
valm = i.second;
}
}
}
if (mxf == -1) {
lant[nod] = nod;
} else {
lant[nod] = lant[mxf];
}
ct[lant[nod]] += valm;
set<pair<i64, int>>::iterator it = s[lant[nod]].lower_bound({K - ct[lant[nod]], 0});
if (it != s[lant[nod]].end())
if ((it -> first) == K - ct[lant[nod]]) {
ans = min(ans, (it -> second) - h);
}
s[lant[nod]].insert({-ct[lant[nod]], h});
for (auto i : g[nod]) {
if (i.first == mxf || i.first == dad)
continue;
int l = lant[i.first];
ct[l] += i.second;
for (auto x : s[l]) {
it = s[lant[nod]].lower_bound({K - ct[lant[nod]] - x.first - ct[l], 0});
if (it != s[lant[nod]].end())
if ((it -> first) == K - ct[lant[nod]] - x.first - ct[l]) {
ans = min(ans, x.second + (it -> second) - 2 * h);
}
}
while (!s[l].empty()) {
pair<i64, int> x = *s[l].begin();
x.first += ct[l];
s[l].erase(s[l].begin());
s[lant[nod]].insert({x.first - ct[lant[nod]], x.second});
}
}
}
int best_path (int n, int k, int h[][2], int l[]) {
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]});
}
ans = n + 1;
dfs(0, 0);
if (ans == n + 1)
ans = -1;
return ans;
}
/*int main() {
int a[11][2]= {0, 1,
0, 2,
2, 3,
3, 4,
4, 5,
0, 6,
6, 7,
6, 8,
8, 9,
8, 10};
int b[11] = {3,4,5,4,6,3,2,5,6,7};
//int a[3][2]= {0, 1, 1, 2, 1, 3 };
//int b[3] = {1, 2, 4};
cout << best_path (11, 12, a, b) << "\n";
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
14436 KB |
Output is correct |
2 |
Correct |
18 ms |
14464 KB |
Output is correct |
3 |
Correct |
19 ms |
14464 KB |
Output is correct |
4 |
Correct |
17 ms |
14464 KB |
Output is correct |
5 |
Correct |
15 ms |
14464 KB |
Output is correct |
6 |
Correct |
17 ms |
14464 KB |
Output is correct |
7 |
Correct |
15 ms |
14464 KB |
Output is correct |
8 |
Correct |
17 ms |
14464 KB |
Output is correct |
9 |
Correct |
15 ms |
14464 KB |
Output is correct |
10 |
Correct |
15 ms |
14464 KB |
Output is correct |
11 |
Correct |
17 ms |
14464 KB |
Output is correct |
12 |
Correct |
15 ms |
14464 KB |
Output is correct |
13 |
Correct |
15 ms |
14464 KB |
Output is correct |
14 |
Correct |
15 ms |
14464 KB |
Output is correct |
15 |
Correct |
15 ms |
14464 KB |
Output is correct |
16 |
Correct |
15 ms |
14464 KB |
Output is correct |
17 |
Correct |
17 ms |
14548 KB |
Output is correct |
18 |
Correct |
19 ms |
14464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
14436 KB |
Output is correct |
2 |
Correct |
18 ms |
14464 KB |
Output is correct |
3 |
Correct |
19 ms |
14464 KB |
Output is correct |
4 |
Correct |
17 ms |
14464 KB |
Output is correct |
5 |
Correct |
15 ms |
14464 KB |
Output is correct |
6 |
Correct |
17 ms |
14464 KB |
Output is correct |
7 |
Correct |
15 ms |
14464 KB |
Output is correct |
8 |
Correct |
17 ms |
14464 KB |
Output is correct |
9 |
Correct |
15 ms |
14464 KB |
Output is correct |
10 |
Correct |
15 ms |
14464 KB |
Output is correct |
11 |
Correct |
17 ms |
14464 KB |
Output is correct |
12 |
Correct |
15 ms |
14464 KB |
Output is correct |
13 |
Correct |
15 ms |
14464 KB |
Output is correct |
14 |
Correct |
15 ms |
14464 KB |
Output is correct |
15 |
Correct |
15 ms |
14464 KB |
Output is correct |
16 |
Correct |
15 ms |
14464 KB |
Output is correct |
17 |
Correct |
17 ms |
14548 KB |
Output is correct |
18 |
Correct |
19 ms |
14464 KB |
Output is correct |
19 |
Correct |
16 ms |
14464 KB |
Output is correct |
20 |
Correct |
16 ms |
14464 KB |
Output is correct |
21 |
Correct |
16 ms |
14592 KB |
Output is correct |
22 |
Correct |
16 ms |
14512 KB |
Output is correct |
23 |
Correct |
16 ms |
14592 KB |
Output is correct |
24 |
Correct |
17 ms |
14592 KB |
Output is correct |
25 |
Correct |
16 ms |
14592 KB |
Output is correct |
26 |
Correct |
21 ms |
14592 KB |
Output is correct |
27 |
Correct |
15 ms |
14464 KB |
Output is correct |
28 |
Correct |
16 ms |
14592 KB |
Output is correct |
29 |
Correct |
19 ms |
14592 KB |
Output is correct |
30 |
Correct |
16 ms |
14592 KB |
Output is correct |
31 |
Correct |
16 ms |
14592 KB |
Output is correct |
32 |
Correct |
16 ms |
14592 KB |
Output is correct |
33 |
Correct |
16 ms |
14592 KB |
Output is correct |
34 |
Correct |
18 ms |
14592 KB |
Output is correct |
35 |
Correct |
16 ms |
14592 KB |
Output is correct |
36 |
Correct |
16 ms |
14592 KB |
Output is correct |
37 |
Correct |
16 ms |
14592 KB |
Output is correct |
38 |
Correct |
17 ms |
14592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
14436 KB |
Output is correct |
2 |
Correct |
18 ms |
14464 KB |
Output is correct |
3 |
Correct |
19 ms |
14464 KB |
Output is correct |
4 |
Correct |
17 ms |
14464 KB |
Output is correct |
5 |
Correct |
15 ms |
14464 KB |
Output is correct |
6 |
Correct |
17 ms |
14464 KB |
Output is correct |
7 |
Correct |
15 ms |
14464 KB |
Output is correct |
8 |
Correct |
17 ms |
14464 KB |
Output is correct |
9 |
Correct |
15 ms |
14464 KB |
Output is correct |
10 |
Correct |
15 ms |
14464 KB |
Output is correct |
11 |
Correct |
17 ms |
14464 KB |
Output is correct |
12 |
Correct |
15 ms |
14464 KB |
Output is correct |
13 |
Correct |
15 ms |
14464 KB |
Output is correct |
14 |
Correct |
15 ms |
14464 KB |
Output is correct |
15 |
Correct |
15 ms |
14464 KB |
Output is correct |
16 |
Correct |
15 ms |
14464 KB |
Output is correct |
17 |
Correct |
17 ms |
14548 KB |
Output is correct |
18 |
Correct |
19 ms |
14464 KB |
Output is correct |
19 |
Correct |
168 ms |
21788 KB |
Output is correct |
20 |
Correct |
155 ms |
21880 KB |
Output is correct |
21 |
Correct |
153 ms |
21624 KB |
Output is correct |
22 |
Correct |
164 ms |
21736 KB |
Output is correct |
23 |
Correct |
182 ms |
22208 KB |
Output is correct |
24 |
Correct |
155 ms |
21724 KB |
Output is correct |
25 |
Correct |
150 ms |
34428 KB |
Output is correct |
26 |
Correct |
120 ms |
41816 KB |
Output is correct |
27 |
Correct |
277 ms |
34296 KB |
Output is correct |
28 |
Correct |
349 ms |
68752 KB |
Output is correct |
29 |
Correct |
370 ms |
66396 KB |
Output is correct |
30 |
Correct |
294 ms |
34300 KB |
Output is correct |
31 |
Correct |
260 ms |
34424 KB |
Output is correct |
32 |
Correct |
332 ms |
34296 KB |
Output is correct |
33 |
Correct |
228 ms |
27164 KB |
Output is correct |
34 |
Correct |
395 ms |
39256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
14436 KB |
Output is correct |
2 |
Correct |
18 ms |
14464 KB |
Output is correct |
3 |
Correct |
19 ms |
14464 KB |
Output is correct |
4 |
Correct |
17 ms |
14464 KB |
Output is correct |
5 |
Correct |
15 ms |
14464 KB |
Output is correct |
6 |
Correct |
17 ms |
14464 KB |
Output is correct |
7 |
Correct |
15 ms |
14464 KB |
Output is correct |
8 |
Correct |
17 ms |
14464 KB |
Output is correct |
9 |
Correct |
15 ms |
14464 KB |
Output is correct |
10 |
Correct |
15 ms |
14464 KB |
Output is correct |
11 |
Correct |
17 ms |
14464 KB |
Output is correct |
12 |
Correct |
15 ms |
14464 KB |
Output is correct |
13 |
Correct |
15 ms |
14464 KB |
Output is correct |
14 |
Correct |
15 ms |
14464 KB |
Output is correct |
15 |
Correct |
15 ms |
14464 KB |
Output is correct |
16 |
Correct |
15 ms |
14464 KB |
Output is correct |
17 |
Correct |
17 ms |
14548 KB |
Output is correct |
18 |
Correct |
19 ms |
14464 KB |
Output is correct |
19 |
Correct |
16 ms |
14464 KB |
Output is correct |
20 |
Correct |
16 ms |
14464 KB |
Output is correct |
21 |
Correct |
16 ms |
14592 KB |
Output is correct |
22 |
Correct |
16 ms |
14512 KB |
Output is correct |
23 |
Correct |
16 ms |
14592 KB |
Output is correct |
24 |
Correct |
17 ms |
14592 KB |
Output is correct |
25 |
Correct |
16 ms |
14592 KB |
Output is correct |
26 |
Correct |
21 ms |
14592 KB |
Output is correct |
27 |
Correct |
15 ms |
14464 KB |
Output is correct |
28 |
Correct |
16 ms |
14592 KB |
Output is correct |
29 |
Correct |
19 ms |
14592 KB |
Output is correct |
30 |
Correct |
16 ms |
14592 KB |
Output is correct |
31 |
Correct |
16 ms |
14592 KB |
Output is correct |
32 |
Correct |
16 ms |
14592 KB |
Output is correct |
33 |
Correct |
16 ms |
14592 KB |
Output is correct |
34 |
Correct |
18 ms |
14592 KB |
Output is correct |
35 |
Correct |
16 ms |
14592 KB |
Output is correct |
36 |
Correct |
16 ms |
14592 KB |
Output is correct |
37 |
Correct |
16 ms |
14592 KB |
Output is correct |
38 |
Correct |
17 ms |
14592 KB |
Output is correct |
39 |
Correct |
168 ms |
21788 KB |
Output is correct |
40 |
Correct |
155 ms |
21880 KB |
Output is correct |
41 |
Correct |
153 ms |
21624 KB |
Output is correct |
42 |
Correct |
164 ms |
21736 KB |
Output is correct |
43 |
Correct |
182 ms |
22208 KB |
Output is correct |
44 |
Correct |
155 ms |
21724 KB |
Output is correct |
45 |
Correct |
150 ms |
34428 KB |
Output is correct |
46 |
Correct |
120 ms |
41816 KB |
Output is correct |
47 |
Correct |
277 ms |
34296 KB |
Output is correct |
48 |
Correct |
349 ms |
68752 KB |
Output is correct |
49 |
Correct |
370 ms |
66396 KB |
Output is correct |
50 |
Correct |
294 ms |
34300 KB |
Output is correct |
51 |
Correct |
260 ms |
34424 KB |
Output is correct |
52 |
Correct |
332 ms |
34296 KB |
Output is correct |
53 |
Correct |
228 ms |
27164 KB |
Output is correct |
54 |
Correct |
395 ms |
39256 KB |
Output is correct |
55 |
Correct |
35 ms |
15828 KB |
Output is correct |
56 |
Correct |
23 ms |
15232 KB |
Output is correct |
57 |
Correct |
87 ms |
21112 KB |
Output is correct |
58 |
Correct |
69 ms |
28396 KB |
Output is correct |
59 |
Correct |
127 ms |
42752 KB |
Output is correct |
60 |
Correct |
301 ms |
69884 KB |
Output is correct |
61 |
Correct |
380 ms |
38876 KB |
Output is correct |
62 |
Correct |
279 ms |
36828 KB |
Output is correct |
63 |
Correct |
408 ms |
37112 KB |
Output is correct |
64 |
Correct |
652 ms |
41872 KB |
Output is correct |
65 |
Correct |
598 ms |
43816 KB |
Output is correct |
66 |
Correct |
356 ms |
64088 KB |
Output is correct |
67 |
Correct |
345 ms |
43620 KB |
Output is correct |
68 |
Correct |
540 ms |
43512 KB |
Output is correct |
69 |
Correct |
507 ms |
43772 KB |
Output is correct |
70 |
Correct |
498 ms |
42236 KB |
Output is correct |