Submission #1108189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108189		eym	Race (IOI11_race)	C++17	9 / 100	3078 ms	14920 KiB

race

#include "race.h"

#include <cassert>
#include <cstdint>
#include <functional>
#include <unordered_map>
#include <vector>

using namespace std;

using i6 = int64_t;

struct Edge {
  int len;
  int dst;
};

vector<vector<Edge>> g;

int res = INT32_MAX;
int n;
int k;

vector<uint8_t> used;

int find_centroid(int root, int total_size) {
  vector<int> sizes(n);
  function<int(int, int)> find_sizes = [&](int p, int u) -> int {
    for (auto e : g[u]) {
      if (e.dst == p || used[e.dst])
        continue;
      sizes[u] += find_sizes(u, e.dst);
    }
    return sizes[u];
  };
  find_sizes(-1, root);

  function<int(int, int)> find_centroid_impl = [&](int p, int u) {
    for (auto e : g[u]) {
      if (e.dst == p || used[e.dst])
        continue;
      if (sizes[e.dst] > total_size / 2) {
        return find_centroid_impl(u, e.dst);
      }
    }
    return u;
  };

  return find_centroid_impl(-1, root);
}

void compute_solution(int root, int total_size) {
  if (used[root])
    return;

  int centroid = find_centroid(root, total_size);
  used[centroid] = 1;

  unordered_map<int, int> comp_sizes;

  {
    vector<int> min_depth_by_dist(k + 1, INT32_MAX);
    vector<int> new_min_depth_by_dist(k + 1, INT32_MAX);
    vector<int> active_dists;

    int comp_size = 0;
    function<void(int, int, int, i6)> walk = [&](int parent, int u, int depth, i6 dist) {
      comp_size++;
      if (dist <= k && depth < res) {  // heuristic
        if (new_min_depth_by_dist[dist] > depth) {
          new_min_depth_by_dist[dist] = depth;
          active_dists.push_back(dist);
        }
      }
      for (auto e : g[u]) {
        if (e.dst == parent || used[e.dst])
          continue;
        walk(u, e.dst, depth + 1, dist + e.len);
      }
    };

    for (auto e : g[centroid]) {
      if (used[e.dst])
        continue;
      comp_size = 0;
      walk(centroid, e.dst, 1, e.len);
      comp_sizes[e.dst] = comp_size;
      for (int dist : active_dists) {
        int depth = new_min_depth_by_dist[dist];
        if (depth >= res)
          continue;
        i6 rem_dist = k - dist;
        if (rem_dist == 0) {
          res = min(res, depth);
        } else if (rem_dist > 0 && rem_dist <= k) {
          if (min_depth_by_dist[rem_dist] != INT32_MAX) {
            res = min(res, depth + min_depth_by_dist[rem_dist]);
          }
        }
      }
      for (int dist : active_dists) {
        if (min_depth_by_dist[dist] > new_min_depth_by_dist[dist]) {
          min_depth_by_dist[dist] = new_min_depth_by_dist[dist];
        }
      }
      new_min_depth_by_dist.assign(k + 1, INT32_MAX);
      active_dists.clear();
    }
  }

  for (auto e : g[centroid]) {
    compute_solution(e.dst, comp_sizes[e.dst]);
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N;
  k = K;
  used.resize(N);
  g.resize(n);
  for (int i = 0; i < N; i++) {
    g[H[i][0]].push_back({L[i], H[i][1]});
    g[H[i][1]].push_back({L[i], H[i][0]});
  }
  compute_solution(0, n);
  return res == INT32_MAX ? -1 : res;
}

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