Submission #483978

#	Time	Username	Problem	Language	Result	Execution time	Memory
483978		arujbansal	Race (IOI11_race)	C++17	31 / 100	194 ms	42636 KiB

race

#include "race.h"

#include <iostream>
#include <vector>

using namespace std;

const int MXN = 2e5 + 5, INF = 1e9 + 5;
vector<pair<int, int>> g[MXN];
int subtree_sz[MXN];
bool vis[MXN];
int N, K;
int ans = INF;

struct two_set {
  pair<int, int> x, y;

  two_set() { x = y = make_pair(INF, INF); }

  void insert(int val, int node) {
    if (val < y.first) y = make_pair(val, node);
    if (x.first > y.first) swap(x, y);
  }

  int query(int exclude_node) {
    if (x.second == exclude_node) return y.first;
    return x.first;
  }

  void work(int u) {
    if (x.second == u) x = make_pair(INF, INF);
    else if (y.second == u) y = make_pair(INF, INF);
    if (x.first > y.first) swap(x, y);
  }

} mn_val[int(1e6) + 5];

int find_centroid(int u, int p, int nodes) {
  if (p != -1) {
    subtree_sz[p] -= subtree_sz[u];
    subtree_sz[u] += subtree_sz[p];
  }

  for (const auto &[v, wt] : g[u])
    if (v != p && !vis[v] && subtree_sz[v] * 2 > nodes)
      return find_centroid(v, u, nodes);

  return u;
}

vector<int> to_reset;

void calc_dist(int u, int p, int len, int depth, bool remove) {
  if (!remove) {
    if (len <= K) mn_val[len].insert(depth, u);
    to_reset.push_back(len);
  } else {
    if (len <= K) {
      mn_val[len].work(u);
    }
  }

  if (len > K) return;

  for (const auto &[v, wt] : g[u])
    if (v != p && !vis[v]) calc_dist(v, u, len + wt, depth + 1, remove);
}

void calc_ans(int u, int p, int len, int depth) {
  if (len < K) ans = min(ans, depth + mn_val[K - len].query(u));
  if (len == K) ans = min(ans, depth);

  if (len > K) return;

  for (const auto &[v, wt] : g[u])
    if (v != p && !vis[v]) calc_ans(v, u, len + wt, depth + 1);
}

void calc_sz(int u, int p) {
  subtree_sz[u] = 1;

  for (const auto &[v, wt] : g[u]) {
    if (v == p) continue;
    calc_sz(v, u);
    subtree_sz[u] += subtree_sz[v];
  }
}

void cd(int u) {
  int centroid = find_centroid(u, -1, subtree_sz[u]);
  vis[centroid] = true;

  for (const auto &[v, wt] : g[centroid])
    if (!vis[v]) calc_dist(v, centroid, wt, 1, false); 

  for (const auto &[v, wt] : g[centroid]) {
    if (!vis[v]) {
      calc_dist(v, centroid, wt, 1, true); 
      calc_ans(v, centroid, wt, 1);
      calc_dist(v, centroid, wt, 1, false); 
    }
  }

  for (const auto &x : to_reset)
    mn_val[x] = two_set();

  to_reset.clear();

  for (const auto &[v, wt] : g[centroid])
    if (!vis[v]) cd(v); 
}

int best_path(int _N, int _K, int _H[][2], int _L[]) {
  N = _N, K = _K;

  for (int i = 0; i < N - 1; i++) {
    _H[i][0]++;
    _H[i][1]++;
    g[_H[i][0]].emplace_back(_H[i][1], _L[i]);
    g[_H[i][1]].emplace_back(_H[i][0], _L[i]);
  }

  calc_sz(1, -1);
  cd(1);

  return (ans < INF ? ans : -1);
}

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