Submission #1259381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259381		salles	Race (IOI11_race)	C++20	21 / 100	3095 ms	7872 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

int melhor(int v, vector<vector< pair<int,int> > >  &adj, vector<int> &visit, int k,int parcial = 0) {
  if(visit[v]) return INT_MAX;
  visit[v] = true;
  if(k==0) {
    return parcial;
  }

  int mi= INT_MAX;
  for(auto &[w,peso]: adj[v]) {
    mi = min(mi, melhor(w,adj,visit,k-peso,parcial+1));
  }
  return mi;
}

int best_path(int n, int k, int H[][2], int L[])
{
  vector<vector< pair<int,int> > >  adj(n);
  for(int i=0;i<n-1;i++) {
    int a = H[i][0];
    int b = H[i][1];
    int w = L[i];
    adj[a].push_back(make_pair(b,w ) );
    adj[b].push_back(make_pair(a,w ) );
  }
  int mi= INT_MAX;
  for(int i=0;i<n;i++) {
    vector<int> visit(n,false);
    int ans = melhor(i,adj,visit,k);
    mi = min(mi, ans);
  }
  if(mi==INT_MAX) mi = -1;
  return mi;
}

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