Submission #1000444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000444		ALTAKEXE	Race (IOI11_race)	C++17	21 / 100	17 ms	9436 KiB

race

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> adj[1010];
int dfs(int x, int p, int rem, int l)
{
  if (rem == 0)
    return l;
  if (rem < 0)
    return 1010;
  int ans = 1010;
  for (auto [y, w] : adj[x])
  {
    if (y == p)
      continue;
    ans = min(ans, dfs(y, x, rem - w, l + 1));
  }
  return ans;
}
int best_path(int n, int k, int h[][2], int l[])
{
  for (int i = 0; i < n - 1; i++)
  {
    adj[h[i][0] + 1].emplace_back(h[i][1] + 1, l[i]);
    adj[h[i][1] + 1].emplace_back(h[i][0] + 1, l[i]);
  }
  int ans = n;
  for (int i = 1; i <= n; i++)
    ans = min(ans, dfs(i, 0, k, 0));
  if (ans >= n)
    return -1;
  else
    return ans;
}

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