Submission #1213810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213810		12baater	Race (IOI11_race)	C++20	21 / 100	3095 ms	10056 KiB

race

#include "race.h"
#include <vector>
#include <iostream>

using namespace std;

const long long MAX = 1E16;


vector<pair<int,int> > adj[200020];
long long current = 0;
long long len = 0;
long long best = MAX;
long long k;
long long n;

void dfs(int node, int parent) {
  if(len >= best) return;
  if(current >= k) {
    if (current == k) {
      best = min(len,best);
    }
    return;
  }
  for(auto [child, cost] : adj[node]) {
    if(child == parent) continue;
    current += cost;
    len++;
    dfs(child, node);
    len--;
    current -= cost;
  }
}


int best_path(int N, int K, int H[][2], int L[]) {
  k = K;
  for (int i = 0; i < N-1; i++){ 
    adj[H[i][0]].emplace_back(H[i][1],L[i]);
    adj[H[i][1]].emplace_back(H[i][0],L[i]);
  }
  for(int i = 0; i < N; i++) {
    current = 0;
    len = 0;
    dfs(i,i);
  }
  return (best == MAX) ? -1 : best;
}

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