Submission #1275366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275366		rafsanamin2020	경주 (Race) (IOI11_race)	C++20	9 / 100	3095 ms	1576 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

int MX = 1200;

vector<vector<pair<int, int>>> adj(MX);

vector<bool> visited(MX, false);

pair<bool, int> dfs(int x, int y, int K, int l = 0, int nh = 0)
{
  if (visited[x])
  {
    return {false, nh};
  }

  if (x == y && l == K)
  {
    return {true, nh};
  }

  visited[x] = true;

  for (pair<int, int> v : adj[x])
  {
    pair<bool, int> ret = dfs(v.first, y, K, l + v.second, nh + 1);

    // cout << x << " " << y << " " << ret.first << " " << ret.second << "__________" << "\n";
    if (ret.first)
    {
      return {true, ret.second};
    }
  }

  return {false, nh};
}

int best_path(int N, int K, int H[][2], int L[])
{

  for (int i = 0; i < N - 1; i++)
  {
    adj[H[i][0]].push_back({H[i][1], L[i]});
    adj[H[i][1]].push_back({H[i][0], L[i]});
  }

  int ans = -1;

  for (int i = 0; i < N; i++)
  {
    for (int j = i + 1; j < N; j++)
    {
      visited = vector<bool>(MX, false);
      pair<bool, int>
          ret = dfs(i, j, K);

      // cout << i << " " << j << " " << ret.first << " " << ret.second << " \n";

      if (ret.first)
      {
        if (ans == -1)
        {
          ans = ret.second;
        }
        else
        {
          ans = min(ans, ret.second);
        }
      }
    }
  }

  return ans;
}

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