Submission #1265776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265776		thecyb	경주 (Race) (IOI11_race)	C++17	100 / 100	727 ms	39876 KiB

race

#include <bits/stdc++.h>

void steroids(const std::string &s = "", const std::string &file_in = ".in", const std::string &file_out = ".out") {
  std::cin.tie(0) -> sync_with_stdio(0);
  if (!s.empty()) {
    freopen((s + file_in).c_str(), "r", stdin);
    freopen((s + file_out).c_str(), "w", stdout);
  }
}

const int N = 2e5;
std::vector<std::pair<int, int>> adj[N];
int sub_sz[N];
bool del[N];
int n, k, ans;
std::map<int, int> current;
std::vector<std::pair<int, int>> to_be_merged;

int dfs_sz(const int &u, const int &p) {
  sub_sz[u] = 1;
  for (const auto &[v, _] : adj[u]) {
    if (v == p || del[v]) continue;
    sub_sz[u] += dfs_sz(v, u);
  }
  return sub_sz[u];
}

int get_centroid(const int &u, const int &p, const int &sz) {
  for (const auto &[v, _] : adj[u]) {
    if (v == p || del[v]) continue;
    if (sub_sz[v] * 2 > sz) return get_centroid(v, u, sz);
  }
  return u;
}

void get_dist_to_centroid(const int &u, const int &p, const int &d, const int &l) {
  if (d > k) return;
  to_be_merged.push_back({d, l});
  for (const auto &[v, w] : adj[u]) {
    if (v == p || del[v]) continue;
    get_dist_to_centroid(v, u, d+w, l+1);
  }
}

void ctd(const int &u) {
  int centroid = get_centroid(u, -1, dfs_sz(u, -1));
  del[centroid] = true;
  current.clear();
  to_be_merged.clear();
  for (const auto &[child, dist] : adj[centroid]) {
    if (del[child]) continue;
    get_dist_to_centroid(child, centroid, dist, 1);
    for (const auto &[d, l] : to_be_merged) {
      if (current.find(k - d) != current.end()) ans = std::min(ans, current[k-d] + l);
      else if (d == k) ans = std::min(ans, l);
    }
    for (const auto &[d, l] : to_be_merged) {
      if (current.count(d)) current[d] = std::min(current[d], l);
      else current[d] = l;
    }
    to_be_merged.clear();
  }
  for (const auto &[nxt, _] : adj[centroid]) {
    if (!del[nxt]) ctd(nxt);
  }
}

int best_path(int nn, int kk, int h[][2], int l[]) {
  n = nn;
  k = kk;
  ans = n;
  for (int i = 0; i < n; i++) {
    int u = h[i][0], v = h[i][1], w = l[i];
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  ctd(0);
  return (ans == n ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'void steroids(const string&, const string&, const string&)':
race.cpp:6:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     freopen((s + file_in).c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:7:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     freopen((s + file_out).c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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