# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
49759 |
2018-06-02T19:44:38 Z |
gs13105 |
Race (IOI11_race) |
C++17 |
|
1625 ms |
39316 KB |
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
using namespace std;
const int MAXN = 200000;
struct edg
{
int x, w;
};
vector<edg> arr[MAXN + 10];
bool chk[MAXN + 10];
int cnt[MAXN + 10];
int k;
int sz;
void f(int x, int p)
{
cnt[x] = 1;
for(edg &e : arr[x])
{
if(chk[e.x] || e.x == p)
continue;
f(e.x, x);
cnt[x] += cnt[e.x];
}
}
int g(int x, int p)
{
bool u = 1;
int sum = 1;
for(edg &e : arr[x])
{
if(chk[e.x] || e.x == p)
continue;
int t = g(e.x, x);
if(t != -1)
return t;
if(cnt[e.x] > sz / 2)
u = 0;
sum += cnt[e.x];
}
if(!u || sz - sum > sz / 2)
return -1;
return x;
}
map<int, int> mem;
vector<pair<int, int>> add;
void h(int x, int p, int w, int l)
{
add.push_back({ w, l });
for(edg &e : arr[x])
{
if(chk[e.x] || e.x == p)
continue;
if(w + e.w <= k)
h(e.x, x, w + e.w, l + 1);
}
}
int solve(int a)
{
f(a, a);
sz = cnt[a];
int c = g(a, a);
assert(c != -1);
mem.clear();
mem[0] = 0;
int res = -1;
for(edg &e : arr[c])
{
if(chk[e.x])
continue;
add.clear();
h(e.x, c, e.w, 1);
for(auto &e : add)
{
auto it = mem.find(k - e.first);
if(it != mem.end())
{
int t = it->second + e.second;
if(res == -1 || t < res)
res = t;
}
}
for(auto &e : add)
{
auto it = mem.find(e.first);
if(it != mem.end())
it->second = min(it->second, e.second);
else
mem[e.first] = e.second;
}
}
chk[c] = 1;
for(edg &e : arr[c])
{
if(chk[e.x])
continue;
int t = solve(e.x);
if(res == -1 || t != -1 && t < res)
res = t;
}
return res;
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i = 0; i < N - 1; i++)
{
arr[H[i][0]].push_back({ H[i][1], L[i] });
arr[H[i][1]].push_back({ H[i][0], L[i] });
}
k = K;
return solve(0);
}
Compilation message
race.cpp: In function 'int solve(int)':
race.cpp:130:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(res == -1 || t != -1 && t < res)
~~~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4984 KB |
Output is correct |
2 |
Correct |
9 ms |
5092 KB |
Output is correct |
3 |
Correct |
8 ms |
5236 KB |
Output is correct |
4 |
Correct |
7 ms |
5332 KB |
Output is correct |
5 |
Correct |
6 ms |
5332 KB |
Output is correct |
6 |
Correct |
7 ms |
5332 KB |
Output is correct |
7 |
Correct |
9 ms |
5332 KB |
Output is correct |
8 |
Correct |
7 ms |
5332 KB |
Output is correct |
9 |
Correct |
7 ms |
5332 KB |
Output is correct |
10 |
Correct |
8 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
8 ms |
5332 KB |
Output is correct |
13 |
Correct |
6 ms |
5332 KB |
Output is correct |
14 |
Correct |
6 ms |
5332 KB |
Output is correct |
15 |
Correct |
7 ms |
5332 KB |
Output is correct |
16 |
Correct |
7 ms |
5332 KB |
Output is correct |
17 |
Correct |
8 ms |
5332 KB |
Output is correct |
18 |
Correct |
7 ms |
5332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4984 KB |
Output is correct |
2 |
Correct |
9 ms |
5092 KB |
Output is correct |
3 |
Correct |
8 ms |
5236 KB |
Output is correct |
4 |
Correct |
7 ms |
5332 KB |
Output is correct |
5 |
Correct |
6 ms |
5332 KB |
Output is correct |
6 |
Correct |
7 ms |
5332 KB |
Output is correct |
7 |
Correct |
9 ms |
5332 KB |
Output is correct |
8 |
Correct |
7 ms |
5332 KB |
Output is correct |
9 |
Correct |
7 ms |
5332 KB |
Output is correct |
10 |
Correct |
8 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
8 ms |
5332 KB |
Output is correct |
13 |
Correct |
6 ms |
5332 KB |
Output is correct |
14 |
Correct |
6 ms |
5332 KB |
Output is correct |
15 |
Correct |
7 ms |
5332 KB |
Output is correct |
16 |
Correct |
7 ms |
5332 KB |
Output is correct |
17 |
Correct |
8 ms |
5332 KB |
Output is correct |
18 |
Correct |
7 ms |
5332 KB |
Output is correct |
19 |
Correct |
7 ms |
5332 KB |
Output is correct |
20 |
Correct |
7 ms |
5332 KB |
Output is correct |
21 |
Correct |
9 ms |
5372 KB |
Output is correct |
22 |
Correct |
8 ms |
5372 KB |
Output is correct |
23 |
Correct |
10 ms |
5372 KB |
Output is correct |
24 |
Correct |
10 ms |
5372 KB |
Output is correct |
25 |
Correct |
10 ms |
5440 KB |
Output is correct |
26 |
Correct |
9 ms |
5440 KB |
Output is correct |
27 |
Correct |
9 ms |
5440 KB |
Output is correct |
28 |
Correct |
9 ms |
5440 KB |
Output is correct |
29 |
Correct |
8 ms |
5440 KB |
Output is correct |
30 |
Correct |
8 ms |
5440 KB |
Output is correct |
31 |
Correct |
8 ms |
5440 KB |
Output is correct |
32 |
Correct |
9 ms |
5440 KB |
Output is correct |
33 |
Correct |
8 ms |
5440 KB |
Output is correct |
34 |
Correct |
7 ms |
5440 KB |
Output is correct |
35 |
Correct |
7 ms |
5440 KB |
Output is correct |
36 |
Correct |
7 ms |
5440 KB |
Output is correct |
37 |
Correct |
7 ms |
5440 KB |
Output is correct |
38 |
Correct |
7 ms |
5440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4984 KB |
Output is correct |
2 |
Correct |
9 ms |
5092 KB |
Output is correct |
3 |
Correct |
8 ms |
5236 KB |
Output is correct |
4 |
Correct |
7 ms |
5332 KB |
Output is correct |
5 |
Correct |
6 ms |
5332 KB |
Output is correct |
6 |
Correct |
7 ms |
5332 KB |
Output is correct |
7 |
Correct |
9 ms |
5332 KB |
Output is correct |
8 |
Correct |
7 ms |
5332 KB |
Output is correct |
9 |
Correct |
7 ms |
5332 KB |
Output is correct |
10 |
Correct |
8 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
8 ms |
5332 KB |
Output is correct |
13 |
Correct |
6 ms |
5332 KB |
Output is correct |
14 |
Correct |
6 ms |
5332 KB |
Output is correct |
15 |
Correct |
7 ms |
5332 KB |
Output is correct |
16 |
Correct |
7 ms |
5332 KB |
Output is correct |
17 |
Correct |
8 ms |
5332 KB |
Output is correct |
18 |
Correct |
7 ms |
5332 KB |
Output is correct |
19 |
Correct |
268 ms |
10824 KB |
Output is correct |
20 |
Correct |
245 ms |
10824 KB |
Output is correct |
21 |
Correct |
276 ms |
11008 KB |
Output is correct |
22 |
Correct |
259 ms |
11128 KB |
Output is correct |
23 |
Correct |
193 ms |
11128 KB |
Output is correct |
24 |
Correct |
141 ms |
11128 KB |
Output is correct |
25 |
Correct |
281 ms |
14404 KB |
Output is correct |
26 |
Correct |
157 ms |
18572 KB |
Output is correct |
27 |
Correct |
350 ms |
18572 KB |
Output is correct |
28 |
Correct |
743 ms |
30588 KB |
Output is correct |
29 |
Correct |
716 ms |
30588 KB |
Output is correct |
30 |
Correct |
363 ms |
30588 KB |
Output is correct |
31 |
Correct |
358 ms |
30588 KB |
Output is correct |
32 |
Correct |
381 ms |
30588 KB |
Output is correct |
33 |
Correct |
598 ms |
30588 KB |
Output is correct |
34 |
Correct |
569 ms |
30588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4984 KB |
Output is correct |
2 |
Correct |
9 ms |
5092 KB |
Output is correct |
3 |
Correct |
8 ms |
5236 KB |
Output is correct |
4 |
Correct |
7 ms |
5332 KB |
Output is correct |
5 |
Correct |
6 ms |
5332 KB |
Output is correct |
6 |
Correct |
7 ms |
5332 KB |
Output is correct |
7 |
Correct |
9 ms |
5332 KB |
Output is correct |
8 |
Correct |
7 ms |
5332 KB |
Output is correct |
9 |
Correct |
7 ms |
5332 KB |
Output is correct |
10 |
Correct |
8 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
8 ms |
5332 KB |
Output is correct |
13 |
Correct |
6 ms |
5332 KB |
Output is correct |
14 |
Correct |
6 ms |
5332 KB |
Output is correct |
15 |
Correct |
7 ms |
5332 KB |
Output is correct |
16 |
Correct |
7 ms |
5332 KB |
Output is correct |
17 |
Correct |
8 ms |
5332 KB |
Output is correct |
18 |
Correct |
7 ms |
5332 KB |
Output is correct |
19 |
Correct |
7 ms |
5332 KB |
Output is correct |
20 |
Correct |
7 ms |
5332 KB |
Output is correct |
21 |
Correct |
9 ms |
5372 KB |
Output is correct |
22 |
Correct |
8 ms |
5372 KB |
Output is correct |
23 |
Correct |
10 ms |
5372 KB |
Output is correct |
24 |
Correct |
10 ms |
5372 KB |
Output is correct |
25 |
Correct |
10 ms |
5440 KB |
Output is correct |
26 |
Correct |
9 ms |
5440 KB |
Output is correct |
27 |
Correct |
9 ms |
5440 KB |
Output is correct |
28 |
Correct |
9 ms |
5440 KB |
Output is correct |
29 |
Correct |
8 ms |
5440 KB |
Output is correct |
30 |
Correct |
8 ms |
5440 KB |
Output is correct |
31 |
Correct |
8 ms |
5440 KB |
Output is correct |
32 |
Correct |
9 ms |
5440 KB |
Output is correct |
33 |
Correct |
8 ms |
5440 KB |
Output is correct |
34 |
Correct |
7 ms |
5440 KB |
Output is correct |
35 |
Correct |
7 ms |
5440 KB |
Output is correct |
36 |
Correct |
7 ms |
5440 KB |
Output is correct |
37 |
Correct |
7 ms |
5440 KB |
Output is correct |
38 |
Correct |
7 ms |
5440 KB |
Output is correct |
39 |
Correct |
268 ms |
10824 KB |
Output is correct |
40 |
Correct |
245 ms |
10824 KB |
Output is correct |
41 |
Correct |
276 ms |
11008 KB |
Output is correct |
42 |
Correct |
259 ms |
11128 KB |
Output is correct |
43 |
Correct |
193 ms |
11128 KB |
Output is correct |
44 |
Correct |
141 ms |
11128 KB |
Output is correct |
45 |
Correct |
281 ms |
14404 KB |
Output is correct |
46 |
Correct |
157 ms |
18572 KB |
Output is correct |
47 |
Correct |
350 ms |
18572 KB |
Output is correct |
48 |
Correct |
743 ms |
30588 KB |
Output is correct |
49 |
Correct |
716 ms |
30588 KB |
Output is correct |
50 |
Correct |
363 ms |
30588 KB |
Output is correct |
51 |
Correct |
358 ms |
30588 KB |
Output is correct |
52 |
Correct |
381 ms |
30588 KB |
Output is correct |
53 |
Correct |
598 ms |
30588 KB |
Output is correct |
54 |
Correct |
569 ms |
30588 KB |
Output is correct |
55 |
Correct |
33 ms |
30588 KB |
Output is correct |
56 |
Correct |
25 ms |
30588 KB |
Output is correct |
57 |
Correct |
192 ms |
30588 KB |
Output is correct |
58 |
Correct |
67 ms |
30588 KB |
Output is correct |
59 |
Correct |
390 ms |
30588 KB |
Output is correct |
60 |
Correct |
1625 ms |
39316 KB |
Output is correct |
61 |
Correct |
433 ms |
39316 KB |
Output is correct |
62 |
Correct |
389 ms |
39316 KB |
Output is correct |
63 |
Correct |
537 ms |
39316 KB |
Output is correct |
64 |
Correct |
1348 ms |
39316 KB |
Output is correct |
65 |
Correct |
398 ms |
39316 KB |
Output is correct |
66 |
Correct |
829 ms |
39316 KB |
Output is correct |
67 |
Correct |
195 ms |
39316 KB |
Output is correct |
68 |
Correct |
535 ms |
39316 KB |
Output is correct |
69 |
Correct |
628 ms |
39316 KB |
Output is correct |
70 |
Correct |
561 ms |
39316 KB |
Output is correct |