Submission #1130978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130978		eshaanagg	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <vector>
#include <map>
#include <functional>
#include <iostream>
using namespace std;

void updateWithMin(map<int, int> &a, int k, int v)
{
  if (a.find(k) == a.end())
    a[k] = v;
  else
    a[k] = min(a[k], v);
}

int get(map<int, int> &a, int k)
{
  return a.find(k) == a.end() ? 1e9 : a[k];
}

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

  for (auto [nk, v] : b)
  {
    int k = nk - l;

    // Find for a complementary end point
    if (a.find(tar - k) != a.end())
    {
      int other = get(a, tar - k);
      updateWithMin(a, 0, v + 1 + other);
    }

    // Set the current end point
    updateWithMin(a, k, v + 1);
  }
}

int main()
{
  int n, k;
  cin >> n >> k;

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

  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, k);
    }

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

  dfs(0, -1);
  cout << (minPaths == n + 1 ? -1 : minPaths) << endl;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccZCCJ1f.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQZ8k0T.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccZCCJ1f.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status