Submission #1130974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130974		eshaanagg	Race (IOI11_race)	C++20	0 / 100	1 ms	428 KiB

race

#include "race.h"
#include <vector>
#include <map>
#include <functional>
#include <iostream>

using namespace std;

void merge(map<int, int> &a, map<int, int> &b, int l)
{
  if (a.size() < b.size())
    swap(a, b);

  for (auto [nk, v] : b)
  {
    int k = nk - l;
    if (a.find(k) != a.end())
      a[k] = min(a[k], v + 1);
    else
      a[k] = v + 1;
  }
}

int best_path(int n, int k, int h[][2], int l[])
{
  cout << "CALLING best_path(" << n << ", " << k << ", {";
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++)
  {
    int u = h[i][0], v = h[i][1];
    u--, v--;
    g[u].push_back({v, l[i]});
    g[v].push_back({u, l[i]});
  }

  vector<map<int, int>> paths(n);
  for (int i = 0; i < n; i++)
    paths[i][k] = 0;

  int minPaths = n + 1;

  function<void(int, int)> dfs = [&](int u, int p)
  {
    for (auto [v, w] : g[u])
    {
      if (v == p)
        continue;
      dfs(v, u);
      merge(paths[u], paths[v], w);
    }

    if (paths[u].find(0) != paths[u].end())
      minPaths = min(minPaths, paths[u][0]);
  };

  dfs(0, -1);
  return minPaths == n + 1 ? -1 : minPaths;
}

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