Submission #1108193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108193		eym	Race (IOI11_race)	C++17	21 / 100	3059 ms	14240 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;

struct CustomHash {
  // Seed with a fixed random value for consistency
  static uint64_t fixedRandom;
  size_t operator()(uint64_t x) const {
    // Use splitmix64 hash function
    x += fixedRandom;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
  }
};

uint64_t CustomHash::fixedRandom = 1337;

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;

  {
    unordered_map<i6, int, CustomHash> min_depth_by_dist;
    unordered_map<i6, int, CustomHash> 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)
        return;

      auto it = new_min_depth_by_dist.find(dist);
      if (it == new_min_depth_by_dist.end() || depth < it->second) {
        new_min_depth_by_dist[dist] = 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;
      new_min_depth_by_dist.clear();
      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)
          continue;
        i6 rem_dist = k - dist;
        if (rem_dist == 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()) {
            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() || depth < it->second) {
          min_depth_by_dist[dist] = depth;
        }
      }
    }
  }

  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: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57