Submission #1012996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012996		aufan	Race (IOI11_race)	C++17	100 / 100	281 ms	76524 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int best_path(int n, int k, int h[][2], int l[]) { 
  vector<vector<pair<int, int>>> v(n);
  for (int i = 0; i < n - 1; i++) {
    int a = h[i][0], b = h[i][1], c = l[i];
    v[a].push_back({b, c});
    v[b].push_back({a, c});
  }

  int tim = -1;
  vector<int> sz(n), big(n, -1), tin(n), tout(n), idx(n), dep(n);
  vector<long long> d(n);

  function<void(int, int)> dfs = [&](int x, int p) {
    sz[x] = 1;
    tin[x] = ++tim;
    idx[tim] = x;

    for (auto [z, c] : v[x]) {
      if (z == p) continue;

      d[z] = d[x] + c;
      dep[z] = dep[x] + 1;

      dfs(z, x);

      sz[x] += sz[z];
      if (big[x] == -1 || sz[z] > sz[big[x]]) big[x] = z;
    }

    tout[x] = tim;
  };

  dfs(0, 0);

  int ans = INF;
  map<long long, int> mp;

  function<void(int, int, bool)> solve = [&](int x, int p, bool del) {
    for (auto [z, c] : v[x]) {
      if (z == p || z == big[x]) continue;

      solve(z, x, 1);
    }

    if (big[x] != -1) solve(big[x], x, 0);

    for (auto [z, c] : v[x]) {
      if (z == p || z == big[x]) continue;
      
      for (int tim = tin[z]; tim <= tout[z]; tim++) {
        int z = idx[tim];
        if (mp.count(d[x] + k - (d[z] - d[x]))) ans = min(ans, mp[d[x] + k - (d[z] - d[x])] + dep[z] - 2 * dep[x]); 
      }
      
      for (int tim = tin[z]; tim <= tout[z]; tim++) {
        int z = idx[tim];
        if (!mp.count(d[z])) mp.insert({d[z], dep[z]});
        else mp[d[z]] = min(mp[d[z]], dep[z]);
      }
    }

    if (mp.count(d[x] + k)) ans = min(ans, mp[d[x] + k] - dep[x]);
    

    if (!mp.count(d[x])) mp.insert({d[x], dep[x]});
    else mp[d[x]] = min(mp[d[x]], dep[x]);

    if (del) mp.clear();
  };

  solve(0, 0, 0);
  if (ans == INF) ans = -1;

  return ans;
}

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