# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
100836 |
2019-03-14T19:53:32 Z |
RafaelSus |
Race (IOI11_race) |
C++14 |
|
636 ms |
35264 KB |
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,k;
bool used_2[200002];
vector<pair<int,int>>g[200002];
int size[200002];
int tree_centroid;
int best[1000002];
const int inf = 1e9;
int ans = 1e9;
void dfs(int node, int dad = -1)
{
size[node] = 1;
for (auto it : g[node])
if (!used_2[it.first] && it.first != dad)
{
dfs(it.first, node);
size[node] += size[it.first];
}
}
void findcentroid(int v, int p, int flo){
// used_1[v]=true;
int zib=0;
for(auto x:g[v]){
if(used_2[x.first] || x.first==p)continue;
if(size[x.first] - 1 >= flo){
zib++;
findcentroid(x.first, v, flo);
break;
}
}
if(zib==0)
tree_centroid=v;
}
void dfs2(int x, int p, int cost, int l, vector<pair<int,int>>&to_ans) {
if (cost <= k)
to_ans.push_back(make_pair(cost, l));
for (auto y : g[x]) {
if (used_2[y.first] || y.first == p)continue;
dfs2(y.first, x, cost + y.second, l + 1, to_ans);
}
}
int solve(int node) {
dfs(node);
// fill(used_1, used_1 + n, false);
int zibil = size[node] - 1;
findcentroid(node, -1, zibil / 2);
node = tree_centroid;
best[0] = 0;
vector<int>del;
vector<pair<int, int>>to_ans;
for (auto x : g[node]) {
int son = x.first;
if (used_2[son])continue;
to_ans.clear();
dfs2(x.first, node, x.second, 1, to_ans);
for (auto it : to_ans)
ans = min(ans, it.second + best[k - it.first]);
for (auto it : to_ans)
{
best[it.first] = min(best[it.first], it.second);
del.push_back(it.first);
}
}
for (auto it : del)
best[it] = inf;
used_2[node] = true;
for (auto it : g[node])
if (!used_2[it.first])
ans = min(ans, solve(it.first));
return ans;
}
int best_path(int N, int _K, int H[][2], int L[])
{
k = _K;
n = N;
int i;
for(i=0; i<N-1; ++i)
{
int x, y, z;
x = H[i][0];
y = H[i][1];
z = L[i];
g[x].push_back(make_pair(y,z));
g[y].push_back(make_pair(x,z));
}
for(i=0; i<=k; ++i) best[i] = inf;
int X = solve(0);
if(X == inf) return -1;
return X;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
5068 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
5092 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
5068 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
5092 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
7 ms |
5120 KB |
Output is correct |
22 |
Correct |
11 ms |
8704 KB |
Output is correct |
23 |
Correct |
10 ms |
8064 KB |
Output is correct |
24 |
Correct |
10 ms |
8448 KB |
Output is correct |
25 |
Correct |
10 ms |
8448 KB |
Output is correct |
26 |
Correct |
8 ms |
6400 KB |
Output is correct |
27 |
Correct |
11 ms |
8192 KB |
Output is correct |
28 |
Correct |
8 ms |
5888 KB |
Output is correct |
29 |
Correct |
8 ms |
6400 KB |
Output is correct |
30 |
Correct |
9 ms |
6528 KB |
Output is correct |
31 |
Correct |
10 ms |
7660 KB |
Output is correct |
32 |
Correct |
9 ms |
7808 KB |
Output is correct |
33 |
Correct |
10 ms |
8192 KB |
Output is correct |
34 |
Correct |
9 ms |
7424 KB |
Output is correct |
35 |
Correct |
9 ms |
8320 KB |
Output is correct |
36 |
Correct |
10 ms |
8704 KB |
Output is correct |
37 |
Correct |
10 ms |
8192 KB |
Output is correct |
38 |
Correct |
9 ms |
7040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
5068 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
5092 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
211 ms |
10704 KB |
Output is correct |
20 |
Correct |
192 ms |
11976 KB |
Output is correct |
21 |
Correct |
167 ms |
12532 KB |
Output is correct |
22 |
Correct |
191 ms |
13216 KB |
Output is correct |
23 |
Correct |
133 ms |
12020 KB |
Output is correct |
24 |
Correct |
88 ms |
12024 KB |
Output is correct |
25 |
Correct |
225 ms |
16112 KB |
Output is correct |
26 |
Correct |
119 ms |
19080 KB |
Output is correct |
27 |
Correct |
262 ms |
18976 KB |
Output is correct |
28 |
Correct |
521 ms |
30080 KB |
Output is correct |
29 |
Correct |
612 ms |
29432 KB |
Output is correct |
30 |
Correct |
268 ms |
19016 KB |
Output is correct |
31 |
Correct |
250 ms |
18936 KB |
Output is correct |
32 |
Correct |
366 ms |
19032 KB |
Output is correct |
33 |
Correct |
393 ms |
17784 KB |
Output is correct |
34 |
Correct |
334 ms |
18552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
5068 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
5092 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
7 ms |
5120 KB |
Output is correct |
22 |
Correct |
11 ms |
8704 KB |
Output is correct |
23 |
Correct |
10 ms |
8064 KB |
Output is correct |
24 |
Correct |
10 ms |
8448 KB |
Output is correct |
25 |
Correct |
10 ms |
8448 KB |
Output is correct |
26 |
Correct |
8 ms |
6400 KB |
Output is correct |
27 |
Correct |
11 ms |
8192 KB |
Output is correct |
28 |
Correct |
8 ms |
5888 KB |
Output is correct |
29 |
Correct |
8 ms |
6400 KB |
Output is correct |
30 |
Correct |
9 ms |
6528 KB |
Output is correct |
31 |
Correct |
10 ms |
7660 KB |
Output is correct |
32 |
Correct |
9 ms |
7808 KB |
Output is correct |
33 |
Correct |
10 ms |
8192 KB |
Output is correct |
34 |
Correct |
9 ms |
7424 KB |
Output is correct |
35 |
Correct |
9 ms |
8320 KB |
Output is correct |
36 |
Correct |
10 ms |
8704 KB |
Output is correct |
37 |
Correct |
10 ms |
8192 KB |
Output is correct |
38 |
Correct |
9 ms |
7040 KB |
Output is correct |
39 |
Correct |
211 ms |
10704 KB |
Output is correct |
40 |
Correct |
192 ms |
11976 KB |
Output is correct |
41 |
Correct |
167 ms |
12532 KB |
Output is correct |
42 |
Correct |
191 ms |
13216 KB |
Output is correct |
43 |
Correct |
133 ms |
12020 KB |
Output is correct |
44 |
Correct |
88 ms |
12024 KB |
Output is correct |
45 |
Correct |
225 ms |
16112 KB |
Output is correct |
46 |
Correct |
119 ms |
19080 KB |
Output is correct |
47 |
Correct |
262 ms |
18976 KB |
Output is correct |
48 |
Correct |
521 ms |
30080 KB |
Output is correct |
49 |
Correct |
612 ms |
29432 KB |
Output is correct |
50 |
Correct |
268 ms |
19016 KB |
Output is correct |
51 |
Correct |
250 ms |
18936 KB |
Output is correct |
52 |
Correct |
366 ms |
19032 KB |
Output is correct |
53 |
Correct |
393 ms |
17784 KB |
Output is correct |
54 |
Correct |
334 ms |
18552 KB |
Output is correct |
55 |
Correct |
16 ms |
5760 KB |
Output is correct |
56 |
Correct |
17 ms |
5824 KB |
Output is correct |
57 |
Correct |
96 ms |
13216 KB |
Output is correct |
58 |
Correct |
43 ms |
12652 KB |
Output is correct |
59 |
Correct |
118 ms |
19848 KB |
Output is correct |
60 |
Correct |
636 ms |
35264 KB |
Output is correct |
61 |
Correct |
250 ms |
17868 KB |
Output is correct |
62 |
Correct |
275 ms |
22180 KB |
Output is correct |
63 |
Correct |
347 ms |
22136 KB |
Output is correct |
64 |
Correct |
581 ms |
22268 KB |
Output is correct |
65 |
Correct |
423 ms |
17332 KB |
Output is correct |
66 |
Correct |
617 ms |
29688 KB |
Output is correct |
67 |
Correct |
151 ms |
23272 KB |
Output is correct |
68 |
Correct |
339 ms |
22552 KB |
Output is correct |
69 |
Correct |
338 ms |
22536 KB |
Output is correct |
70 |
Correct |
323 ms |
22128 KB |
Output is correct |