Submission #1264518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264518		thecyb	Race (IOI11_race)	C++17	100 / 100	344 ms	100592 KiB

race

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ff first
#define ss second

void steroids() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
}

const int N = 2e5;
const int inf = 1e9;
std::vector<std::pair<int, int>> adj[N];
int h[N][2];
int l[N];
int d[N];
ll dis_from_root[N];
int n, k;
int ans;
std::map<ll, int> paths[N];

void dfs(const int &u, const int &par, const ll &cur_dist, const int &cur_height) {
  paths[u][cur_dist] = cur_height;
  dis_from_root[u] = cur_dist;
  d[u] = cur_height;
  for (const auto &p : adj[u]) {
    if (p.ff != par){
      dfs(p.ff, u, cur_dist + p.ss, cur_height + 1);
    }
  }
}

void smol_to_larg(const int &u, const int &p) {
  ll target = 0LL + k + 2 * dis_from_root[u];
  for (const auto &[v, w] : adj[u]) {
    if (v != p) {
      smol_to_larg(v, u);
      if (paths[v].size() > paths[u].size()) paths[u].swap(paths[v]);
      for (const auto &[len, dis] : paths[v]) {
        if (paths[u].find(target - len) != paths[u].end()) {
          ans = std::min(ans, dis + paths[u][target-len] - 2 * d[u]);
        }
      }
      for (const auto &p : paths[v]) {
        if (paths[u].find(p.ff) == paths[u].end()) {
          paths[u].insert(p);
        } else {
          paths[u][p.ff] = std::min(paths[u][p.ff], p.ss);
        }
      }
    }
  }
}

int best_path(int Num, int Req, int h[][2], int l[]){
  n = Num;
  k = Req;
  ans = inf;
  for (int i = 0; i < n-1; i++) {
    adj[h[i][0]].push_back({h[i][1], l[i]});
    adj[h[i][1]].push_back({h[i][0], l[i]});
  }
  d[0] = 0;
  dfs(0, -1, 0, 0);
  smol_to_larg(0, -1);
  return ans == inf ? -1 : ans;
}

/*int main() {
  steroids();
  int nn, kk;
  std::cin >> nn >> kk;
  for (int i = 0; i < nn-1; i++) {
    std::cin >> h[i][0] >> h[i][1];
  }
  for (int i = 0; i < nn-1; i++) {
    std::cin >> l[i];
  }
  std::cout << best_path(nn, kk, h, l);
}
*/

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