Submission #691314

#	Time	Username	Problem	Language	Result	Execution time	Memory
691314		zeroesandones	Race (IOI11_race)	C++17	21 / 100	22 ms	2900 KiB

race

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

using ll = long long;
using vi = vector<ll>;
using pi = pair<long long, long long>;

#define pb emplace_back
#define fr first
#define sc second

const int mxN = 1005;
const ll inf = 1e15;

vector<pi> adj[mxN];
pi dep[mxN];

void dfs(int x, int p, int d, int l) {
  dep[x].fr = d;
  dep[x].sc = l;
  for(auto [i, w] : adj[x]) {
    if(i != p) {
      dfs(i, x, d + 1, l + w);
    }
  }
}

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]);
  }

  ll ans = inf;
  for(int i = 0; i < N; ++i) {
    pi id = {0, 0};
    fill(dep, dep + mxN, id);
    dfs(i, -1, 0, 0);
    for(int j = 0; j < N; ++j) {
      if(dep[j].sc == K)
        ans = min(ans, dep[j].fr);
    }
  }

  return (ans == inf ? -1 : ans);
}

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