Submission #1291550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291550		ghammazhassan	Race (IOI11_race)	C++20	100 / 100	342 ms	103360 KiB

race

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

#define MAX_N 200005
using ll = long long;

int n;
ll k;
ll di[MAX_N];
int dep[MAX_N];

vector<pair<int,int>> a[MAX_N];
set<pair<ll,int>> s[MAX_N];

const int INF = 1e9;

int dfs(int x, int p) {
  int ans = INF;

  s[x].insert({di[x], dep[x]});

  int heavy = -1;
  int mx = 0;

  for (auto &e : a[x]) {
    int y = e.first;
    int w = e.second;
    if (y == p) continue;

    di[y] = di[x] + (ll)w;
    dep[y] = dep[x] + 1;

    ans = min(ans, dfs(y, x));

    if (s[y].size() > mx) {
      mx = s[y].size();
      heavy = y;
    }
  }

  if (heavy == -1) return ans;

  swap(s[x], s[heavy]);

  for (auto &e : a[x]) {
    int y = e.first;
    if (y == p) continue;

    for (auto &pr : s[y]) {
      ll dist_child = pr.first;
      int depth_child = pr.second;

      
      ll required = (k - (dist_child - di[x])) + di[x];

      auto it = s[x].lower_bound({required, -1ll});
      if (it != s[x].end() && (*it).first == required) {
        int depth_here = (*it).second;
        ans = min(ans, depth_child + depth_here - 2 * dep[x]);
      }
    }

    for (auto &pr : s[y]) s[x].insert(pr);
  }

  return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N;
  k = (ll)K;


  for (int i = 0; i < n - 1; ++i) {
    int u = H[i][0], v = H[i][1], w = L[i];
    a[u].push_back({v, w});
    a[v].push_back({u, w});
  }

  di[0] = 0;
  dep[0] = 0;
  int ans = dfs(0, -1);
  if (ans == INF) return -1;
  return ans;
}

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