oj.uz

Submission #855827

# Submission time Handle Problem Language Result Execution time Memory
855827 2023-10-02T01:58:00 Z rxlfd314 Factories (JOI14_factories) C++17
0 / 100
 14 ms 56288 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using arl2 = array<ll, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)

static constexpr int mxN = 500000;
static vt<ari2> adj[mxN];
static vt<arl2> cdal[mxN];
static vt<int> cd[mxN];
static ll best[mxN];
static int N;

void Init(int _N, int A[], int B[], int D[]) {
  N = _N;
  FOR(i, 0, N-2) {
    adj[A[i]].push_back({B[i], D[i]});
    adj[B[i]].push_back({A[i], D[i]});
  }
  int szs[N] = {};
  bool dead[N] = {};
  function<int(int, int)> gs = [&](int i, int p) {
    szs[i] = 1;
    for (auto [j, _] : adj[i])
      if (!dead[j] && j != p)
        szs[i] += gs(j, i);
    return szs[i];
  };
  function<int(int, int, int)> fc = [&](int i, int n, int p) {
    for (auto [j, _] : adj[i])
      if (!dead[j] && j != p && szs[j] > n >> 1)
        return fc(j, n, i);
    return i;
  };
  int root;
  function<void(int, int)> init = [&](int i, int p) {
    int c = fc(i, gs(i, i), i);
    dead[c] = true;
    if (~p)
      cd[p].push_back(c);
    else
      root = c;
    for (auto [j, _] : adj[c])
      if (!dead[j])
        init(j, c);
  };
  init(0, -1);
  
  const int L = 32 - __builtin_clz(N);
  vt<vt<int>> lift(N, vt<int>(L));
  int tin[N], tout[N], timer = 0;
  ll depth[N] = {};
  function<void(int, int)> pc = [&](int i, int p) {
    lift[i][0] = p;
    tin[i] = timer++;
    for (auto [j, v] : adj[i]) {
      if (j == p)
        continue;
      depth[j] = depth[i] + v;
      pc(j, i);
    }
    tout[i] = timer - 1;
  };
  pc(0, 0);
  FOR(j, 1, L-1)
    FOR(i, 0, N-1)
      lift[i][j] = lift[lift[i][j-1]][j-1];
  auto ia = [&](int a, int b) {
    return tin[a] <= tin[b] && tin[b] <= tout[a];
  };
  auto LCA = [&](int a, int b) {
    if (ia(a, b))
      return a;
    if (ia(b, a))
      return b;
    FOR(i, L-1, 0)
      a = ia(lift[a][i], b) ? a : lift[a][i];
    return lift[a][0];
  };
  auto dist = [&](int a, int b) {
    return depth[a] + depth[b] - 2 * depth[LCA(a, b)];
  };
  function<void(int)> pc_cdal = [&](int i) {
    cdal[i].push_back({i, 0});
    for (int j : cd[i]) {
      for (auto [a, _] : cdal[i])
        cdal[j].push_back({a, dist(a, j)});
      pc_cdal(j);
    }
  };
  pc_cdal(root);
  memset(best, 0x3f, sizeof(best));
}

ll Query(int S, int X[], int T, int Y[]) {
  FOR(i, 0, S-1)
    for (auto [a, b] : cdal[X[i]])
      chmin(best[a], b);
  ll ret = LLONG_MAX;
  FOR(i, 0, T-1)
    for (auto [a, b] : cdal[Y[i]])
      chmin(ret, best[a] + b);
  FOR(i, 0, S-1)
    for (auto [a, _] : cdal[X[i]])
      best[a] = 0x3f3f3f3f3f3f3f3f;
  return ret;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 56288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 55972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 56288 KB Output isn't correct
2 Halted 0 ms 0 KB -