Submission #1108829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108829		eym	Race (IOI11_race)	C++17	21 / 100	3059 ms	12496 KiB

race

#include "race.h"

#include <sys/resource.h>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#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, 1);
  function<void(int, int)> find_sizes = [&](int p, int u) -> void {
    for (auto e : g[u]) {
      if (e.dst == p || used[e.dst])
        continue;
      find_sizes(u, e.dst);
      sizes.at(u) += sizes.at(e.dst);
    }
    // cout << u << " has size " << sizes[u] << " in " << root << " (in `find_sizes`)" << endl;
  };
  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;
      // cout << e.dst << " has size " << sizes.at(e.dst) << " in " << root << endl;
      if (sizes[e.dst] > total_size / 2) {
        return find_centroid_impl(u, e.dst);
      }
    }
    return u;
  };
  auto centroid = find_centroid_impl(-1, root);
  // cout << "the subtree of " << root << " has " << total_size << " vertices to process and
  // centroid "
  //      << centroid << endl;
  return centroid;
}

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;

  {
    unordered_map<i6, int> min_depth_by_dist;
    unordered_map<i6, int> new_min_depth_by_dist;

    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
        auto it = new_min_depth_by_dist.find(dist);
        if (it == new_min_depth_by_dist.end()) {
          new_min_depth_by_dist[dist] = depth;
        } else {
          new_min_depth_by_dist[dist] = min(it->second, depth);
        }
      }
      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 (auto& [dist, depth] : new_min_depth_by_dist) {
        if (depth >= res)  // heuristic
          continue;
        i6 rem_dist = k - dist;
        if (rem_dist == 0) {
          assert(depth > 0);
          res = min(res, depth);
        } else if (rem_dist > 0) {
          auto it = min_depth_by_dist.find(rem_dist);
          if (it != min_depth_by_dist.end()) {
            assert(depth + it->second > 0);
            res = min(res, depth + it->second);
          }
        }
      }
      for (auto& [dist, depth] : new_min_depth_by_dist) {
        auto it = min_depth_by_dist.find(dist);
        if (it == min_depth_by_dist.end()) {
          min_depth_by_dist[dist] = depth;
        } else {
          min_depth_by_dist[dist] = min(it->second, depth);
        }
      }
      new_min_depth_by_dist.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 - 1; i++) {
    g[H[i][0]].push_back({L[i], H[i][1]});
    g[H[i][1]].push_back({L[i], H[i][0]});
  }
  // for (int i = 0; i < N; i++) {
  //   cout << i << " -> ";
  //   for (auto e : g[i]) {
  //     cout << e.dst << " ";
  //   }
  //   cout << endl;
  // }
  compute_solution(0, n);
  return res == INT32_MAX ? -1 : res;
}

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