Submission #170896

#	Time	Username	Problem	Language	Result	Execution time	Memory
170896		WLZ	Race (IOI11_race)	C++14	100 / 100	1964 ms	62728 KiB

race

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

const int INF = 0x3f3f3f3f;

int n, k, ans = INF;
vector< map<int, int> > g;
vector<int> sz;
map<int, int> len, new_len;

int dfs(int u, int par) {
  sz[u] = 1;
  for (auto& v : g[u]) {
    if (v.first != par) {
      sz[u] += dfs(v.first, u);
    }
  }
  return sz[u];
}

int find_centroid(int u, int par, int n) {
  for (auto& v : g[u]) {
    if (v.first != par && sz[v.first] > n / 2) {
      return find_centroid(v.first, u, n);
    }
  }
  return u;
}

void find_path(int u, int par, int cur_dist, int cur_len) {
  if (cur_dist > k) {
    return;
  }
  if (len.count(k - cur_dist)) {
    ans = min(ans, len[k - cur_dist] + cur_len);
  }
  if (!new_len.count(cur_dist)) {
    new_len[cur_dist] = cur_len;
  } else {
    new_len[cur_dist] = min(new_len[cur_dist], cur_len);
  }
  for (auto& v : g[u]) {
    if (v.first != par) {
      find_path(v.first, u, cur_dist + v.second, cur_len + 1);
    }
  }
}

void find_path(int u, int par) {
  len.clear();
  new_len.clear();
  len[0] = 0;
  for (auto& v : g[u]) {
    if (v.first != par) {
      find_path(v.first, u, v.second, 1);
      for (auto& p : new_len) {
        if (!len.count(p.first)) {
          len[p.first] = p.second;
        } else {
          len[p.first] = min(len[p.first], p.second);
        }
      }
      new_len.clear();
    }
  }
}

void decompose(int u, int par) {
  int n = dfs(u, par);
  int centroid = find_centroid(u, par, n);
  find_path(centroid, par);
  vector<int> tmp;
  for (auto& v : g[centroid]) {
    tmp.push_back(v.first);
  }
  for (auto& v : tmp) {
    if (v != par) {
      g[centroid].erase(v);
      g[v].erase(centroid);
      decompose(v, centroid);
    }
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N, k = K;
  g.resize(n);
  sz.resize(n);
  for (int i = 0; i < n - 1; i++) {
    g[H[i][0]].insert({H[i][1], L[i]});
    g[H[i][1]].insert({H[i][0], L[i]});
  }
  decompose(0, -1);
  if (ans == INF) {
    return -1;
  }
  return ans;
}

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