Submission #422788

#	Time	Username	Problem	Language	Result	Execution time	Memory
422788		SuhaibSawalha1	Race (IOI11_race)	C++17	0 / 100	1 ms	204 KiB

race

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

vector<vector<array<int, 2>>> adj;
int n, k, ans = 2e9, nodes;
vector<int> sub;
bitset<200000> is_cent; 
map<int, int> mp2;

void precalc (int u, int p = -1) {
  sub[u] = 1;
  ++nodes;
  for (auto &v : adj[u]) {
    if (!is_cent[v[0]] && v[0] ^ p) {
      precalc(v[0], u);
      sub[u] += sub[v[0]];
    }
  }
}

int centroid (int u, int p = -1) {
  bool is = nodes - sub[u] <= nodes / 2;
  int heavy = -1;
  for (auto &v : adj[u]) {
    if (!is_cent[v[0]] && v[0] ^ p) {
      is &= sub[v[0]] <= nodes / 2;
      if (heavy == -1 || sub[heavy] < sub[v[0]]) {
        heavy = v[0];
      }
    }
  }
  return is ? u : centroid(heavy, u);
}

void update (map<int, int> &m, int k, int v) {
  if (m.count(k)) {
    m[k] = min(m[k], v);
  }
  else {
    m[k] = v;
  }
}

void dfs (int u, int p, int sum, int d) {
  if (sum > k) {
    return;
  }
  update(mp2, sum, d);
  for (auto &v : adj[u]) {
    if (!is_cent[v[0]] && v[0] ^ p) {
      dfs(v[0], u, sum + v[1], d + 1);
    }
  }
}

void decompose (int u = 0) {
  nodes = 0;
  precalc(u);
  int cent = centroid(u);
  map<int, int> mp;
  mp[0] = 0;
  is_cent[cent] = 1;
  for (auto &v : adj[cent]) {
    if (is_cent[v[0]]) {
      continue;
    }
    mp2.clear();
    dfs(v[0], u, v[1], 1);
    for (auto &p : mp2) {
      if (mp.count(k - p.first)) {
        ans = min(ans, p.second + mp[k - p.first]);
      }
    }
    for (auto &p : mp2) {
      update(mp, p.first, p.second);
    }
  }
  for (auto &v : adj[cent]) {
    if (!is_cent[v[0]]) {
      decompose(v[0]);
    }
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N;
  k = K;
  adj.resize(n);
  sub.resize(n);
  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]});
  }
  decompose();
  return ans == 2e9 ? -1 : ans;
}

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