Submission #97859

#	Time	Username	Problem	Language	Result	Execution time	Memory
97859		kitsu_hi	Race (IOI11_race)	C++14	100 / 100	2225 ms	44700 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;

vector< vector< pair<int, int> > > edges;
int size_of_subtree[200005], blocked[200005];
map <int, int> big, small;
int answer = INT_MAX;

void get_size_of_subtree(int current_node, int parent) {
  size_of_subtree[current_node] = 1;
  for (auto child : edges[current_node]) {
    if (child.first != parent) {
      get_size_of_subtree(child.first, current_node);
      size_of_subtree[current_node] += size_of_subtree[child.first];
    } 
  }
}

int get_centroid(int current_node) {
  for (auto child : edges[current_node]) {
    if (blocked[child.first] == 0 && size_of_subtree[child.first] > size_of_subtree[current_node] / 2) {
      int total_size = size_of_subtree[current_node];
      size_of_subtree[current_node] -= size_of_subtree[child.first];
      size_of_subtree[child.first] = total_size;
      return get_centroid(child.first); 
    }
  }
  return current_node;
}

void dfs(int current_node, int parent, int sum, int depth) {
  if (small.find(sum) == small.end()) small[sum] = depth;
  else small[sum] = min(small[sum], depth);
  for (auto child : edges[current_node]) {
    if (blocked[child.first] == 0 && child.first != parent) {
      dfs(child.first, current_node, sum + child.second, depth + 1);
    }
  }
}

void solve(int current_node, int sum) {
  big.clear();
  current_node = get_centroid(current_node);
  blocked[current_node] = 1;
  big[0] = 0;
  for (auto child : edges[current_node]) {
    small.clear();
    if (blocked[child.first] == 1) continue;
    dfs(child.first, current_node, child.second, 1);
    for (auto value : small) {
      if (big.find(sum - value.first) != big.end()) answer = min(answer, big[sum - value.first] + small[value.first]);
    }
    for (auto value : small) {
      if (big.find(value.first) == big.end()) big[value.first] = small[value.first];
      else big[value.first] = min(big[value.first], small[value.first]);
    }
  }
  for (auto child : edges[current_node]) {
    if (blocked[child.first] == 0) solve(child.first, sum); 
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  edges.resize(N+1);
  for (int i = 0; i < N - 1; i++) {
    edges[H[i][0]].push_back(make_pair(H[i][1], L[i]));
    edges[H[i][1]].push_back(make_pair(H[i][0], L[i]));
  }
  get_size_of_subtree(0, -1);
  solve(0, K);
  if (answer == INT_MAX) answer = -1;
  return answer;
}

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