Submission #864066

#	Time	Username	Problem	Language	Result	Execution time	Memory
864066		blackslex	Race (IOI11_race)	C++17	21 / 100	3081 ms	42792 KiB

race

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

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

const int MxN = 2e5 + 5, MxK = 1e6 + 5;
ll d, sz[MxN], rpar, mn[MxK], ans = 1e12;
vector<pii> v[MxN], u[MxN];
vector<ll> t;
bool f[MxN];

ll dfssz (ll cur, ll par) {
  sz[cur] = 1;
  for (auto &[x, y]: v[cur]) if (par != x && !f[x]) sz[cur] += dfssz(x, cur);
  return sz[cur];
}

ll cen (ll cur, ll par, ll now) {
  for (auto &[x, y]: v[cur]) if (par != x && !f[x] && sz[x] * 2 > now) return cen(x, cur, now);
  return cur;
}

void dfs (ll cur, ll par, ll dist, ll len) {
  if (dist > d) return; u[rpar].emplace_back(dist, len); t.emplace_back(dist);
  for (auto &[x, y]: v[cur]) if (par != x && !f[x]) dfs(x, cur, dist + y, len + 1);
}

void upd (ll cur) {
  for (auto &[x, y]: u[cur]) if (x <= d && mn[d - x] != 1e12) ans = min(ans, mn[d - x] + y);
  for (auto &[x, y]: u[cur]) mn[x] = min(mn[x], y);
}

void decom (ll cur) {
  cur = cen(cur, 0, dfssz(cur, 0)); f[cur] = 1; mn[0] = 0;
  for (auto &[x, y]: v[cur]) if (!f[x]) rpar = x, dfs(x, 0, y, 1), upd(x);
  for (auto &e: t) mn[e] = 1e12;
  for (auto &[x, y]: v[cur]) if (!f[x]) u[x].clear();
  for (auto &[x, y]: v[cur]) if (!f[x]) decom(x);
}

int best_path(int n, int K, int h[][2], int l[]) {
  d = K;
  for (int i = 0; i < MxK; i++) mn[i] = 1e12;
  for (int i = 0; i < n - 1; i++) h[i][0]++, h[i][1]++;
  for (int i = 0; i < n - 1; i++) v[h[i][0]].emplace_back(h[i][1], l[i]), v[h[i][1]].emplace_back(h[i][0], l[i]);
  decom(1);
  return (ans == 1e12 ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'void dfs(ll, ll, ll, ll)':
race.cpp:26:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   26 |   if (dist > d) return; u[rpar].emplace_back(dist, len); t.emplace_back(dist);
      |   ^~
race.cpp:26:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   26 |   if (dist > d) return; u[rpar].emplace_back(dist, len); t.emplace_back(dist);
      |                         ^

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