Submission #864393

#	Time	Username	Problem	Language	Result	Execution time	Memory
864393		computerbox	Race (IOI11_race)	C++14	0 / 100	7 ms	27736 KiB

race

#include <bits/stdc++.h>

using namespace std;


vector<pair<int, int> >adj[1000010];
int ans = INT_MAX;

vector<long long>preff;

void dfs(int v, int p, int k)
{
  long long sum = preff.back();
  if(sum == k)
  {
    ans = min(ans, (int)preff.size() - 1);
  }
  if(sum > k)
  {
    int need = sum - k;
    int indx = lower_bound(preff.begin(), preff.end(), need) - preff.begin();
    if(preff[indx] == need)
    {
      ans = min(ans, (int)preff.size() - indx - 1);
    }
  }

  for(auto to: adj[v])
  {
    if(to.first == p)continue;
    preff.push_back(preff.back() + to.second);
    dfs(to.first, v, k);
  }

  preff.pop_back();
}

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]});
  }
  preff.push_back(0);
  dfs(0, 0, K);
  if(ans == INT_MAX)return -1;
  return ans;
}

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