Submission #978163

#	Time	Username	Problem	Language	Result	Execution time	Memory
978163		kilkuwu	Race (IOI11_race)	C++17	100 / 100	304 ms	92240 KiB

race

#include "race.h"

#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

int best_path(int N, int K, int H[][2], int L[]) {

  std::vector<std::vector<std::pair<int, int>>> adj(N);

  for (int i = 0; i + 1 < N; i++) {
    int u = H[i][0], v = H[i][1], w = L[i];
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  int ans = 1e9;

  struct Answer {
    int64_t dw = 0;
    int dc = 0;
    std::map<int64_t, int> mp;

    int size() const {
      return (int) mp.size();
    }
  };

  auto merge = [&](Answer& l, Answer& r) {
    if (l.size() < r.size()) std::swap(l, r);

    for (auto [k, v] : r.mp) {

      auto required = K - k - r.dw - l.dw; // all the added weight is loss
      auto it = l.mp.find(required);
      
      if (it != l.mp.end()) {
        ans = std::min(ans, it->second + v + l.dc + r.dc);
      }
      // after that's done we merge
    }

    for (auto [k, v] : r.mp) {
      auto nk = k + r.dw - l.dw;
      auto nv = v + r.dc - l.dc;
      auto it = l.mp.find(nk);

      if (it == l.mp.end()) {
        l.mp[nk] = nv;
      } else {
        it->second = std::min(it->second, nv);
      }
    }
  };

  auto dfs = [&](auto self, int u, int p) -> Answer {
    Answer re;
    re.mp[0] = 0;

    for (auto [v, w] : adj[u]) {
      if (v == p) continue;
      auto res = self(self, v, u);
      
      res.dw += w;
      res.dc++;
      merge(re, res);
    }

    dbg(u, re.dc, re.dw, re.mp);
    return re;
  };

  dfs(dfs, 0, 0);

  return ans < 1e9 ? ans : -1;
}

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