Submission #1000668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000668		ALTAKEXE	Race (IOI11_race)	C++17	0 / 100	159 ms	11608 KiB

race

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> adj[1010];
unordered_map<int, int> dp[200000];

void dfs(int node, int parent, int K, int &min_edges)
{
  dp[node][0] = 0; 

  for (auto &edge : adj[node])
  {
    int next_node = edge.first;
    int length = edge.second;

    if (next_node == parent)
      continue;

    dfs(next_node, node, K, min_edges);
    unordered_map<int, int> new_paths;
    for (auto &path : dp[node])
    {
      for (auto &sub_path : dp[next_node])
      {
        int combined_length = path.first + sub_path.first + length;
        if (combined_length == K)
        {
          min_edges = min(min_edges, path.second + sub_path.second + 1);
        }
        if (combined_length < K)
        {
          if (new_paths.find(combined_length) == new_paths.end() ||
              new_paths[combined_length] > path.second + sub_path.second + 1)
          {
            new_paths[combined_length] = path.second + sub_path.second + 1;
          }
        }
      }
    }
    for (auto &p : new_paths)
    {
      if (dp[node].find(p.first) == dp[node].end() || dp[node][p.first] > p.second)
      {
        dp[node][p.first] = p.second;
      }
    }
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  for (int i = 0; i < N; i++)
  {
    adj[i].clear();
    dp[i].clear();
  }
  for (int i = 0; i < N - 1; i++)
  {
    int u = H[i][0], v = H[i][1], length = L[i];
    adj[u].push_back({v, length});
    adj[v].push_back({u, length});
  }

  int min_edges = INT_MAX;
  for (int i = 0; i < N; i++)
  {
    dfs(i, -1, K, min_edges);
  }

  return (min_edges == INT_MAX) ? -1 : min_edges;
}

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