oj.uz

Submission #821742

# Submission time Handle Problem Language Result Execution time Memory
821742 2023-08-11T14:51:18 Z WLZ Factories (JOI14_factories) C++17
100 / 100
 5132 ms 149768 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

const long long LINF = (long long) 1e18;

int n, max_log;
vector< vector< pair<int, int> > > g;
vector<int> sz, cd;
vector<bool> used;

int calc_sizes(int u, int par) {
  sz[u] = 1;
  for (auto &[v, w] : g[u]) if (v != par && !used[v]) sz[u] += calc_sizes(v, u);
  return sz[u];
}

int find_centroid(int u, int par, int cur_sz) {
  for (auto &[v, w] : g[u]) if (v != par && !used[v] && sz[v] > cur_sz / 2) return find_centroid(v, u, cur_sz);
  return u;
}

void decompose(int u, int par) {
  int centroid = find_centroid(u, par, calc_sizes(u, par));
  cd[centroid] = par; used[centroid] = true;
  for (auto &[v, w] : g[centroid]) if (!used[v] && v != par) decompose(v, centroid);
}

int dfs_cnt = 0;
vector< vector<int> > up;
vector<int> dfs_in, dfs_out;
vector<long long> depth;

void dfs(int u, int par) {
  dfs_in[u] = dfs_cnt++;
  up[u][0] = par;
  for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
  for (auto &[v, w] : g[u]) {
    if (v == par) continue;
    depth[v] = depth[u] + w;
    dfs(v, u);
  }
  dfs_out[u] = dfs_cnt++;
}

bool is_anc(int u, int v) {
  return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
}

int lca(int u, int v) {
  if (is_anc(u, v)) return u;
  if (is_anc(v, u)) return v;
  for (int i = max_log; i >= 0; i--) if (!is_anc(up[u][i], v)) u = up[u][i];
  return up[u][0];
}

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

vector<long long> closest;

void Init(int N, int A[], int B[], int D[]) {
  n = N;
  max_log = ceil(log2(n + 1));
  g.resize(n);
  for (int i = 0; i < n - 1; i++) { 
    g[A[i]].emplace_back(B[i], D[i]);
    g[B[i]].emplace_back(A[i], D[i]);
  }
  cd.resize(n);
  sz.resize(n); used.assign(n, false);
  decompose(0, -1);
  depth.resize(n); depth[0] = 0;
  dfs_in.resize(n); dfs_out.resize(n);
  up.assign(n, vector<int>(max_log + 1));
  dfs(0, 0);
  closest.assign(n, LINF);
}



long long Query(int S, int X[], int T, int Y[]) {
  stack<int> st;
  for (int i = 0; i < S; i++) {
    for (int u = X[i]; u != -1; u = cd[u]) {
      closest[u] = min(closest[u], dist(X[i], u));
      st.push(u);
    }
  }
  long long ans = LINF;
  for (int i = 0; i < T; i++) {
    for (int u = Y[i]; u != -1; u = cd[u]) {
      ans = min(ans, closest[u] + dist(Y[i], u));
    }
  }
  while (!st.empty()) {
    closest[st.top()] = LINF;
    st.pop();
  }
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 852 KB Output is correct
2 Correct 302 ms 12324 KB Output is correct
3 Correct 559 ms 12408 KB Output is correct
4 Correct 535 ms 12536 KB Output is correct
5 Correct 438 ms 12732 KB Output is correct
6 Correct 183 ms 12492 KB Output is correct
7 Correct 503 ms 12416 KB Output is correct
8 Correct 502 ms 12424 KB Output is correct
9 Correct 440 ms 12752 KB Output is correct
10 Correct 153 ms 12360 KB Output is correct
11 Correct 507 ms 12348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2013 ms 118112 KB Output is correct
3 Correct 2751 ms 121340 KB Output is correct
4 Correct 596 ms 119596 KB Output is correct
5 Correct 3172 ms 149768 KB Output is correct
6 Correct 2897 ms 122608 KB Output is correct
7 Correct 1496 ms 44532 KB Output is correct
8 Correct 262 ms 45280 KB Output is correct
9 Correct 1257 ms 48988 KB Output is correct
10 Correct 1498 ms 46132 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 852 KB Output is correct
2 Correct 302 ms 12324 KB Output is correct
3 Correct 559 ms 12408 KB Output is correct
4 Correct 535 ms 12536 KB Output is correct
5 Correct 438 ms 12732 KB Output is correct
6 Correct 183 ms 12492 KB Output is correct
7 Correct 503 ms 12416 KB Output is correct
8 Correct 502 ms 12424 KB Output is correct
9 Correct 440 ms 12752 KB Output is correct
10 Correct 153 ms 12360 KB Output is correct
11 Correct 507 ms 12348 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2013 ms 118112 KB Output is correct
14 Correct 2751 ms 121340 KB Output is correct
15 Correct 596 ms 119596 KB Output is correct
16 Correct 3172 ms 149768 KB Output is correct
17 Correct 2897 ms 122608 KB Output is correct
18 Correct 1496 ms 44532 KB Output is correct
19 Correct 262 ms 45280 KB Output is correct
20 Correct 1257 ms 48988 KB Output is correct
21 Correct 1498 ms 46132 KB Output is correct
22 Correct 2893 ms 122448 KB Output is correct
23 Correct 2922 ms 124876 KB Output is correct
24 Correct 5132 ms 126356 KB Output is correct
25 Correct 4445 ms 127808 KB Output is correct
26 Correct 4560 ms 123416 KB Output is correct
27 Correct 4645 ms 148116 KB Output is correct
28 Correct 729 ms 124160 KB Output is correct
29 Correct 4845 ms 122844 KB Output is correct
30 Correct 4883 ms 122292 KB Output is correct
31 Correct 4870 ms 123004 KB Output is correct
32 Correct 1551 ms 50840 KB Output is correct
33 Correct 287 ms 46140 KB Output is correct
34 Correct 807 ms 42368 KB Output is correct
35 Correct 832 ms 42448 KB Output is correct
36 Correct 1418 ms 42992 KB Output is correct
37 Correct 1413 ms 42984 KB Output is correct