Submission #857816

#	Time	Username	Problem	Language	Result	Execution time	Memory
857816		Bach21	Race (IOI11_race)	C++14	0 / 100	9 ms	28760 KiB

race

#include <bits/stdc++.h>
#include "race.h"
const int nmax=1e6+5;
using namespace std;
vector<pair<int,int> > h[nmax];
int sum,d;
int res=0x3f;
bool visted[nmax];
void dfs(int s,int k)
{
  visted[s]=1;
  if (sum==k)
  {
    res=min(res,d);
  }
  for (auto x : h[s])
  {
    if (!visted[x.first])
    {
      sum+=x.second;
      d++;
      dfs(x.first,k);
      visted[x.first]=0;
      sum-=x.second;
      d--;
    }
  }
}
int best_path(int N,int K,int H[][2],int L[])
{
  for (int i=0;i<N-1;i++)
  {
    int a=H[i][0];
    int b=H[i][1];
    h[a].push_back({b,L[i]});
    h[b].push_back({a,L[i]});
  }
  for (int i=1;i<=N;i++)
  {
    memset(visted,0,sizeof visted);
    d=0;
    sum=0;
    dfs(i,K);
  }
  if (res==0x3f) res=-1;
  return res;
}

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