| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 401999 |
2021-05-11T07:03:53 Z |
mshandilya |
Race (IOI11_race) |
C++14 |
|
1207 ms |
215500 KB |
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
long long goal;
int min_edge;
std::vector<std::list<pair<int, int>>> adj_list;
std::vector<std::unordered_map<long long, int>> dist_keymap;
std::vector<int> subtree_size;
void dfs(int root, int parent,
int parent_centroid,
int edge_dist, long long km_dist,
std::vector<pair<long long, int>>& subtree_dist) {
if(dist_keymap[parent_centroid].count(goal-km_dist) and dist_keymap[parent_centroid][goal-km_dist]+edge_dist<min_edge)
min_edge = dist_keymap[parent_centroid][goal-km_dist]+edge_dist;
pair<long long, int> d = {km_dist, edge_dist};
subtree_dist.emplace_back(d);
subtree_size[root] = 1;
for(auto& i : adj_list[root]) {
if(i.first!=parent) {
dfs(i.first, root, parent_centroid, edge_dist+1, km_dist+i.second, subtree_dist);
subtree_size[root] += subtree_size[i.first];
}
}
return;
}
void build_tree(int root, int tree_size) {
int centroid = root;
bool found = false;
while(!found){
found = true;
for(auto& i : adj_list[centroid])
if(subtree_size[i.first]>tree_size/2) {
subtree_size[centroid] = tree_size - subtree_size[i.first];
subtree_size[i.first] = tree_size;
centroid = i.first;
found = false;
}
}
dist_keymap[centroid][0] = 0;
for(auto& child : adj_list[centroid]) {
std::list<pair<int, int>>::iterator i = adj_list[child.first].begin();
for(; i!=adj_list[child.first].end(); i++)
if((*i).first == centroid)
break;
adj_list[child.first].erase(i);
std::vector<pair<long long, int>> subtree_dist;
dfs(child.first, centroid, centroid, 1, child.second, subtree_dist);
for(auto& i : subtree_dist) {
if(!dist_keymap[centroid].count(i.first) or dist_keymap[centroid][i.first]>i.second)
dist_keymap[centroid][i.first] = i.second;
}
build_tree(child.first, subtree_size[child.first]);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
goal = K;
min_edge = N+1;
adj_list.assign(N, std::list<pair<int, int>> ());
subtree_size.resize(N);
dist_keymap.assign(N, unordered_map<long long, int> ());
for(int i = 0; i<N-1; i++) {
adj_list[H[i][0]].push_back({H[i][1], L[i]});
adj_list[H[i][1]].push_back({H[i][0], L[i]});
}
std::vector<pair<long long, int>> garbage_vector;
dfs(0, -1, 0, -N, -(long long)2e5, garbage_vector);
build_tree(0, N);
if(min_edge<N)
return min_edge;
else
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
3 ms |
696 KB |
Output is correct |
| 22 |
Correct |
3 ms |
716 KB |
Output is correct |
| 23 |
Correct |
3 ms |
844 KB |
Output is correct |
| 24 |
Correct |
3 ms |
716 KB |
Output is correct |
| 25 |
Correct |
3 ms |
692 KB |
Output is correct |
| 26 |
Correct |
3 ms |
716 KB |
Output is correct |
| 27 |
Correct |
2 ms |
588 KB |
Output is correct |
| 28 |
Correct |
3 ms |
716 KB |
Output is correct |
| 29 |
Correct |
3 ms |
716 KB |
Output is correct |
| 30 |
Correct |
3 ms |
716 KB |
Output is correct |
| 31 |
Correct |
3 ms |
716 KB |
Output is correct |
| 32 |
Correct |
3 ms |
692 KB |
Output is correct |
| 33 |
Correct |
3 ms |
844 KB |
Output is correct |
| 34 |
Correct |
3 ms |
844 KB |
Output is correct |
| 35 |
Correct |
3 ms |
716 KB |
Output is correct |
| 36 |
Correct |
3 ms |
820 KB |
Output is correct |
| 37 |
Correct |
3 ms |
716 KB |
Output is correct |
| 38 |
Correct |
4 ms |
820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
250 ms |
40416 KB |
Output is correct |
| 20 |
Correct |
269 ms |
41420 KB |
Output is correct |
| 21 |
Correct |
252 ms |
39704 KB |
Output is correct |
| 22 |
Correct |
257 ms |
38780 KB |
Output is correct |
| 23 |
Correct |
330 ms |
57688 KB |
Output is correct |
| 24 |
Correct |
179 ms |
38196 KB |
Output is correct |
| 25 |
Correct |
278 ms |
41644 KB |
Output is correct |
| 26 |
Correct |
158 ms |
44084 KB |
Output is correct |
| 27 |
Correct |
426 ms |
85484 KB |
Output is correct |
| 28 |
Correct |
1207 ms |
215500 KB |
Output is correct |
| 29 |
Correct |
1159 ms |
211400 KB |
Output is correct |
| 30 |
Correct |
434 ms |
85596 KB |
Output is correct |
| 31 |
Correct |
445 ms |
85628 KB |
Output is correct |
| 32 |
Correct |
530 ms |
85344 KB |
Output is correct |
| 33 |
Correct |
652 ms |
94256 KB |
Output is correct |
| 34 |
Correct |
1044 ms |
164972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
3 ms |
696 KB |
Output is correct |
| 22 |
Correct |
3 ms |
716 KB |
Output is correct |
| 23 |
Correct |
3 ms |
844 KB |
Output is correct |
| 24 |
Correct |
3 ms |
716 KB |
Output is correct |
| 25 |
Correct |
3 ms |
692 KB |
Output is correct |
| 26 |
Correct |
3 ms |
716 KB |
Output is correct |
| 27 |
Correct |
2 ms |
588 KB |
Output is correct |
| 28 |
Correct |
3 ms |
716 KB |
Output is correct |
| 29 |
Correct |
3 ms |
716 KB |
Output is correct |
| 30 |
Correct |
3 ms |
716 KB |
Output is correct |
| 31 |
Correct |
3 ms |
716 KB |
Output is correct |
| 32 |
Correct |
3 ms |
692 KB |
Output is correct |
| 33 |
Correct |
3 ms |
844 KB |
Output is correct |
| 34 |
Correct |
3 ms |
844 KB |
Output is correct |
| 35 |
Correct |
3 ms |
716 KB |
Output is correct |
| 36 |
Correct |
3 ms |
820 KB |
Output is correct |
| 37 |
Correct |
3 ms |
716 KB |
Output is correct |
| 38 |
Correct |
4 ms |
820 KB |
Output is correct |
| 39 |
Correct |
250 ms |
40416 KB |
Output is correct |
| 40 |
Correct |
269 ms |
41420 KB |
Output is correct |
| 41 |
Correct |
252 ms |
39704 KB |
Output is correct |
| 42 |
Correct |
257 ms |
38780 KB |
Output is correct |
| 43 |
Correct |
330 ms |
57688 KB |
Output is correct |
| 44 |
Correct |
179 ms |
38196 KB |
Output is correct |
| 45 |
Correct |
278 ms |
41644 KB |
Output is correct |
| 46 |
Correct |
158 ms |
44084 KB |
Output is correct |
| 47 |
Correct |
426 ms |
85484 KB |
Output is correct |
| 48 |
Correct |
1207 ms |
215500 KB |
Output is correct |
| 49 |
Correct |
1159 ms |
211400 KB |
Output is correct |
| 50 |
Correct |
434 ms |
85596 KB |
Output is correct |
| 51 |
Correct |
445 ms |
85628 KB |
Output is correct |
| 52 |
Correct |
530 ms |
85344 KB |
Output is correct |
| 53 |
Correct |
652 ms |
94256 KB |
Output is correct |
| 54 |
Correct |
1044 ms |
164972 KB |
Output is correct |
| 55 |
Correct |
23 ms |
5488 KB |
Output is correct |
| 56 |
Correct |
16 ms |
3912 KB |
Output is correct |
| 57 |
Correct |
183 ms |
37600 KB |
Output is correct |
| 58 |
Correct |
77 ms |
29540 KB |
Output is correct |
| 59 |
Correct |
377 ms |
89540 KB |
Output is correct |
| 60 |
Correct |
1085 ms |
208180 KB |
Output is correct |
| 61 |
Correct |
466 ms |
90156 KB |
Output is correct |
| 62 |
Correct |
428 ms |
85228 KB |
Output is correct |
| 63 |
Correct |
544 ms |
85420 KB |
Output is correct |
| 64 |
Correct |
971 ms |
135340 KB |
Output is correct |
| 65 |
Correct |
943 ms |
128532 KB |
Output is correct |
| 66 |
Correct |
1157 ms |
210556 KB |
Output is correct |
| 67 |
Correct |
281 ms |
59568 KB |
Output is correct |
| 68 |
Correct |
641 ms |
94100 KB |
Output is correct |
| 69 |
Correct |
637 ms |
95160 KB |
Output is correct |
| 70 |
Correct |
664 ms |
89588 KB |
Output is correct |
