Submission #491727

#	Time	Username	Problem	Language	Result	Execution time	Memory
491727		Soumya1	Race (IOI11_race)	C++17	0 / 100	8 ms	14540 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int mxN = 2e5 + 5;
vector<pair<int, int>> ad[mxN];
map<int, int> mp[mxN];
int ans = 1e9;
void dfs(int u, int p, int k, int d, int h) {
  mp[u][d] = h;
  for (auto [v, w] : ad[u]) {
    if (v == p) continue;
    dfs(v, u, k, d + w, h + 1);
    if (mp[v].size() > mp[u].size()) {
      swap(mp[u], mp[v]);
    }
    for (auto [i, j] : mp[v]) {
      if (k + 2 * d - i >= 0 && mp[u].find(k + 2 * d - i) != mp[u].end()) {
        ans = min(ans, mp[u][k + 2 * d - i] + mp[v][i] - 2 * h);
      }
    }
    for (auto [i, j] : mp[v]) {
      if (!mp[u][i]) mp[u][i] = j;
      else mp[u][i] = min(mp[u][i], j);
    }
  }
}
int best_path(int N, int K, int H[][2], int L[]) {
  for (int i = 0; i < N - 1; i++) {
    ad[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
    ad[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
  }
  dfs(1, -1, K, 0, 1);
  cout << ans << endl;
  if (ans == 1e9) ans = -1;
  return ans;
}

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