Submission #401999

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
401999	2021-05-11 07:03:53	mshandilya	Race (IOI11_race)	C++14	100 / 100	1207 ms	215500 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57