oj.uz

Submission #698946

# Submission time Handle Problem Language Result Execution time Memory
698946 2023-02-15T00:00:34 Z MattTheNub Factories (JOI14_factories) C++17
100 / 100
 4238 ms 276548 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 980 KB Output is correct
2 Correct 395 ms 14092 KB Output is correct
3 Correct 515 ms 14188 KB Output is correct
4 Correct 399 ms 13508 KB Output is correct
5 Correct 530 ms 13728 KB Output is correct
6 Correct 182 ms 13476 KB Output is correct
7 Correct 495 ms 13528 KB Output is correct
8 Correct 509 ms 13652 KB Output is correct
9 Correct 505 ms 13780 KB Output is correct
10 Correct 194 ms 13512 KB Output is correct
11 Correct 481 ms 13500 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1885 ms 230300 KB Output is correct
3 Correct 2273 ms 236620 KB Output is correct
4 Correct 729 ms 230992 KB Output is correct
5 Correct 3039 ms 254260 KB Output is correct
6 Correct 2496 ms 233164 KB Output is correct
7 Correct 1234 ms 57280 KB Output is correct
8 Correct 331 ms 57912 KB Output is correct
9 Correct 1262 ms 60636 KB Output is correct
10 Correct 1318 ms 58448 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 980 KB Output is correct
2 Correct 395 ms 14092 KB Output is correct
3 Correct 515 ms 14188 KB Output is correct
4 Correct 399 ms 13508 KB Output is correct
5 Correct 530 ms 13728 KB Output is correct
6 Correct 182 ms 13476 KB Output is correct
7 Correct 495 ms 13528 KB Output is correct
8 Correct 509 ms 13652 KB Output is correct
9 Correct 505 ms 13780 KB Output is correct
10 Correct 194 ms 13512 KB Output is correct
11 Correct 481 ms 13500 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1885 ms 230300 KB Output is correct
14 Correct 2273 ms 236620 KB Output is correct
15 Correct 729 ms 230992 KB Output is correct
16 Correct 3039 ms 254260 KB Output is correct
17 Correct 2496 ms 233164 KB Output is correct
18 Correct 1234 ms 57280 KB Output is correct
19 Correct 331 ms 57912 KB Output is correct
20 Correct 1262 ms 60636 KB Output is correct
21 Correct 1318 ms 58448 KB Output is correct
22 Correct 2522 ms 231920 KB Output is correct
23 Correct 2264 ms 234232 KB Output is correct
24 Correct 3868 ms 234028 KB Output is correct
25 Correct 3685 ms 261260 KB Output is correct
26 Correct 3512 ms 257620 KB Output is correct
27 Correct 4238 ms 276548 KB Output is correct
28 Correct 909 ms 258992 KB Output is correct
29 Correct 3358 ms 257400 KB Output is correct
30 Correct 3352 ms 256640 KB Output is correct
31 Correct 3325 ms 257288 KB Output is correct
32 Correct 1512 ms 73080 KB Output is correct
33 Correct 332 ms 69748 KB Output is correct
34 Correct 929 ms 66512 KB Output is correct
35 Correct 1027 ms 66476 KB Output is correct
36 Correct 1253 ms 67008 KB Output is correct
37 Correct 1256 ms 66988 KB Output is correct