Submission #698946

#	Time	Username	Problem	Language	Result	Execution time	Memory
698946		MattTheNub	Factories (JOI14_factories)	C++17	100 / 100	4238 ms	276548 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
template <class T> using v = vector<T>;
using int2 = pair<int, int>;
using ll = long long;
using ll2 = pair<ll, ll>;

#define f first
#define s second
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';

v<v<int2>> adj;
v<int> tour, depth, parent, sz, st, en, mask;
v<ll> rdist;

void dfs_sz(int node, int pt) {
  sz[node] = 1;
  for (auto next : adj[node]) {
    if (next.f != pt && parent[next.f] == -2) {
      dfs_sz(next.f, node);
      sz[node] += sz[next.f];
    }
  }
}

int timer = 0;
void dfs(int node, int pt) {
  st[node] = timer++;
  tour.push_back(node);
  for (auto next : adj[node]) {
    if (next.f != pt) {
      depth[next.f] = depth[node] + 1;
      rdist[next.f] = rdist[node] + next.s;
      dfs(next.f, node);
      tour.push_back(node);
      timer++;
    }
  }
  en[node] = timer - 1;
}

int centroid(int n, int node, int pt) {
  for (auto next : adj[node]) {
    if (next.f != pt && sz[next.f] > n / 2 && parent[next.f] == -2)
      return centroid(n, next.f, node);
  }
  return node;
}

void decomp(int node, int pt) {
  dfs_sz(node, pt);
  node = centroid(sz[node], node, pt);

  parent[node] = pt;
  for (auto next : adj[node]) {
    if (parent[next.f] == -2) {
      decomp(next.f, node);
    }
  }
}
int n;
v<ll2> cdist;
v<int2> dat[20];

void compute(int d, int l, int r) {
  if (l == r)
    return;
  int mid = (l + r) / 2;
  dat[d][mid] = {depth[tour[mid]], tour[mid]};
  for (int i = mid - 1; i >= l; i--) {
    dat[d][i] = min(dat[d][i + 1], {depth[tour[i]], tour[i]});
  }
  dat[d][mid + 1] = {depth[tour[mid + 1]], tour[mid + 1]};
  for (int i = mid + 2; i <= r; i++) {
    dat[d][i] = min(dat[d][i - 1], {depth[tour[i]], tour[i]});
  }
  for (int i = mid + 1; i <= r; i++)
    mask[i] |= (1 << d);
  compute(d + 1, l, mid);
  compute(d + 1, mid + 1, r);
}

void Init(int N, int A[], int B[], int D[]) {
  cdist.assign(N, {LLONG_MAX / 2, -1});
  n = N;
  adj.resize(N);
  for (int i = 0; i < N - 1; i++) {
    adj[A[i]].push_back({B[i], D[i]});
    adj[B[i]].push_back({A[i], D[i]});
  }
  parent.assign(N, -2);
  rdist.resize(N);
  sz.resize(N);
  st.resize(N);
  en.resize(N);
  depth.resize(N);
  dfs(0, -1);
  for (int i = 0; i < 20; i++) {
    dat[i].resize(tour.size());
  }
  mask.resize(tour.size());
  compute(0, 0, tour.size() - 1);
  decomp(0, -1);
}

int lca(int u, int v) {
  if (u == v)
    return u;

  if (st[u] > st[v])
    swap(u, v);

  int i = __builtin_ctz(mask[st[u]] ^ mask[st[v]]);
  return min(dat[i][st[u]], dat[i][st[v]]).s;
}

ll dist(int u, int v) { return rdist[v] + rdist[u] - 2 * rdist[lca(u, v)]; }

int q = 0;
long long Query(int S, int X[], int T, int Y[]) {
  q++;
  for (int i = 0; i < S; i++) {
    for (int u = X[i]; u != -1; u = parent[u]) {
      if (cdist[u].s != q) {
        cdist[u].f = LLONG_MAX;
        cdist[u].s = q;
      }
      cdist[u].f = min(cdist[u].f, dist(X[i], u));
      // dbg(cdist[X[i]].f);
    }
  }
  // cdist contains the min. distance to any vertex in X (in theory)
  ll r = LLONG_MAX / 2;
  for (int i = 0; i < T; i++) {
    for (int u = Y[i]; u != -1; u = parent[u]) {
      if (cdist[u].s == q)
        r = min(r, dist(u, Y[i]) + cdist[u].f);
    }
  }
  return r;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67