Submission #698902

#	Time	Username	Problem	Language	Result	Execution time	Memory
698902		MattTheNub	Factories (JOI14_factories)	C++17	0 / 100	8073 ms	234580 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> depth, parent, sz;
v<ll2> up[20];
v<ll> rdist;

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

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

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;

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);
  depth.resize(N);
  rdist.resize(N);
  for (int i = 0; i < 20; i++) {
    up[i].resize(N);
  }
  sz.resize(N);
  dfs(0, -1);
  for (int i = 1; i < 20; i++) {
    for (int j = 0; j < n; j++) {
      if (up[i - 1][j].f == -1) {
        up[i][j].f = -1;
      } else {
        up[i][j] = {up[i - 1][up[i - 1][j].f].f,
                    up[i - 1][j].s + up[i - 1][up[i - 1][j].f].s};
      }
    }
  }
  decomp(0, -1);
}

ll dist(int u, int v) {
  if (depth[u] > depth[v])
    swap(u, v);

  ll dist = 0;
  for (int i = 0; i < 20; i++) {
    if ((depth[v] - depth[u]) & (1 << i)) {
      dist += up[i][v].s;
      v = up[i][v].f;
    }
  }

  if (u == v)
    return dist;
  for (int i = 19; i >= 0; i--) {
    if (up[i][u].f != -1 && up[i][u].f != up[i][v].f) {
      dist += up[i][u].s + up[i][v].s;
      u = up[i][u].f;
      v = up[i][v].f;
    }
  }

  return dist + up[0][u].s + up[0][v].s;
}

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: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67