Submission #987697

#	Time	Username	Problem	Language	Result	Execution time	Memory
987697		Tsagana	Race (IOI11_race)	C++14	0 / 100	3 ms	8540 KiB

race

#include "race.h"

#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second

using namespace std;

vector<pair<int, int>> adj[200001];
int mn = 2e9;
void dfs(int s, int val, int cnt, int key, int vis[]) {
  if (val == key) {mn = min(mn, cnt); return ;}

  for (auto i: adj[s]) {
    if (vis[i.F] || val + i.S > key) continue ;
    vis[i.F] = 1; dfs(i.F, val + i.S, cnt + 1, key, vis); vis[i.F] = 0;
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  for (int i = 0; i < N-1; i++) {
    adj[H[i][0]].pb({H[i][1], L[i]});
    adj[H[i][1]].pb({H[i][0], L[i]});
  }
  int a[N] = {0};
  for (int i = 0; i < N; i++) dfs(i, 0, 0, K, a);
  return mn;
}

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