Submission #1313195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313195		Agageldi	경주 (Race) (IOI11_race)	C++20	21 / 100	3094 ms	7604 KiB

race

#include "bits/stdc++.h"
// #include "grader.cpp"
#include "race.h"
using namespace std;

#define MAXN 500005
#define ll long long
#define f first
#define s second

vector <pair<int,int>> E[MAXN];

int ans = -1;

void solve(int x,int p,int K,int nm) {
  if(!K) {
    if(!~ans) ans = nm;
    ans = min(ans,nm);
  }
  for(auto i : E[x]) {
    if(i.f == p) continue;
    if(K >= i.s) solve(i.f, x, K - i.s, nm + 1);
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  for(int i = 0; i < N - 1; i++) {
    E[H[i][0]].push_back({H[i][1], L[i]});
    E[H[i][1]].push_back({H[i][0], L[i]});
  }
  for(int i = 0; i < N; i++) {
    solve(i, 0, K, 0);
  }
  return ans;
}

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