Submission #1130994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130994		eshaanagg	Race (IOI11_race)	C++20	9 / 100	115 ms	25156 KiB

race

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int best_path(int n, int k, int edges[][2], int wt[])
{
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++)
  {
    int u = edges[i][0], v = edges[i][1], w = wt[i];
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }

  vector<int> depth(n);
  vector<ll> dis(n);

  function<void(int, int, int)> dfs = [&](int u, int p, int d)
  {
    depth[u] = d;
    for (auto [v, w] : g[u])
    {
      if (v == p)
        continue;
      dis[v] = dis[u] + w;
      dfs(v, u, d + 1);
    }
  };
  dfs(0, -1, 0);

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

  int minPaths = n + 1;

  auto merge = [&](map<int, int> &a, map<int, int> &b, int u, int v) -> void
  {
    if (a.size() < b.size())
      swap(a, b);

    for (auto [netDist, netDepth] : b)
    {
      // a + b - 2 * me = k
      // a = k + 2 * me - b
      ll key = k + 2 * netDist - dis[u];
      if (a.count(key))
        minPaths = min(minPaths, a[key] + netDepth - 2 * depth[u]);

      if (a.count(netDist))
        a[netDist] = min(a[netDist], netDepth);
      else
        a[netDist] = netDepth;
    }
  };

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

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

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