oj.uz

Submission #289515

# Submission time Handle Problem Language Result Execution time Memory
289515 2020-09-02T17:31:38 Z Haunted_Cpp Factories (JOI14_factories) C++17
33 / 100
 8000 ms 206004 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long i64;
 
const int MAX_N = 500000 + 5;
const int MAX_K = 21;
const i64 INF = 1e18;
 
vector<pair<int, int>> g[MAX_N];
 
int sub[MAX_N], del[MAX_N], par[MAX_N], in[MAX_N], pw[MAX_K], L[2 * MAX_N];

vector<vector<int>> table(2 * MAX_N, vector<int>(MAX_K));
vector<int> depth(MAX_N);
 
i64 d[MAX_N], best_way[MAX_N];
 
int calc_subtree(int node, int p) {
  sub[node] = 1;
  for (auto to : g[node]) {
    if (to.first != p && !del[to.first]) {
      sub[node] += calc_subtree(to.first, node);
    }
  }
  return sub[node];
}
 
int calc_centroid(int node, int p, const int tam) {
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p && sub[to.first] > tam / 2) {
      return calc_centroid(to.first, node, tam);
    }
  }
  return node;
}
 
void decompose(int node, int p) {
  const int centroid = calc_centroid(node, -1, calc_subtree(node, -1));
  del[centroid] = 1;
  par[centroid] = p;
  for (auto to : g[centroid]) {
    if (!del[to.first]) {
      decompose(to.first, centroid);
    }
  }
}

vector<int> euler;
 
void prep(int node, int p) {
  in[node] = euler.size();
  euler.emplace_back(node);
  for (auto to : g[node]) {
    if (to.first != p) {
      d[to.first] = d[node] + to.second;
      depth[to.first] = depth[node] + 1;
      prep(to.first, node);
      euler.emplace_back(node);
    }
  }
}
 
void build_lca() {
  const int n = euler.size();
  for (int i = 0; i < n; i++) {
    table[i][0] = euler[i];
  }
  for (int i = 1; i <= n; i++) {
    L[i] = log2(i);
  }
  for (int j = 1; j < MAX_K; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
      int H1 = depth[table[i][j - 1]];
      int H2 = depth[table[i + (1 << (j - 1))][j - 1]];
      table[i][j] = (H1 < H2 ? table[i][j - 1] : table[i + (1 << (j - 1))][j - 1]);
    }
  }
}
 
int lca(int u, int v) {
  if (u == v) return u;
  if (in[u] > in[v]) {
    swap(u, v);
  }
  int st = in[u];
  int et = in[v];
  const int k = L[(et - st + 1)];
  int H1 = depth[table[st][k]];
  int H2 = depth[table[et - pw[k] + 1][k]];
  return (H1 < H2 ? table[st][k] : table[et - pw[k] + 1][k]);
}
 
i64 get_dist(int u, int v) {
  return d[u] + d[v] - 2LL * d[lca(u, v)];
}
 
void paint(int node, bool reset) {
  int start_location = node;
  while(node != -1) {
    if (reset) {
      best_way[node] = INF;
    } else {
      best_way[node] = min(best_way[node], get_dist(start_location, node));
    }
    node = par[node];
  }
}
 
i64 solve(int node) {
  int start_location = node;
  i64 mn = INF;
  while(node != -1) {
    mn = min(mn, get_dist(start_location, node) + best_way[node]);
    node = par[node];
  }
  return mn;
}
 
void Init(int N, int A[], int B[], int D[]) {
  for (int i = 0; i < N - 1; i++) {
    const int st = A[i];
    const int et = B[i];
    const int w = D[i];
    g[st].emplace_back(et, w);
    g[et].emplace_back(st, w);
  }
  prep(0, -1);
  for (int i = 0; i < MAX_K; i++) {
    pw[i] = (1 << i);
  }
  build_lca();
  decompose(0, -1);
  for (int i = 0; i < MAX_N; i++) {
    best_way[i] = INF;
  }
}
 
i64 Query(int S, int X[], int T, int Y[]) {
  i64 mn = INF;
  for (int i = 0; i < S; i++) {
    paint(X[i], false);
  }
  for (int i = 0; i < T; i++) {
    mn = min(mn, solve(Y[i]));
  }
  for (int i = 0; i < S; i++) {
    paint(X[i], true);
  }
  return mn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 135928 KB Output is correct
2 Correct 678 ms 146172 KB Output is correct
3 Correct 790 ms 144120 KB Output is correct
4 Correct 807 ms 144132 KB Output is correct
5 Correct 889 ms 144248 KB Output is correct
6 Correct 471 ms 144120 KB Output is correct
7 Correct 793 ms 144200 KB Output is correct
8 Correct 798 ms 144124 KB Output is correct
9 Correct 885 ms 144376 KB Output is correct
10 Correct 472 ms 143992 KB Output is correct
11 Correct 787 ms 144140 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 135544 KB Output is correct
2 Correct 3711 ms 190044 KB Output is correct
3 Correct 4881 ms 187564 KB Output is correct
4 Correct 1405 ms 187536 KB Output is correct
5 Correct 6425 ms 206004 KB Output is correct
6 Correct 5194 ms 190756 KB Output is correct
7 Correct 3318 ms 155876 KB Output is correct
8 Correct 856 ms 156652 KB Output is correct
9 Correct 3637 ms 159216 KB Output is correct
10 Correct 3349 ms 157144 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 135928 KB Output is correct
2 Correct 678 ms 146172 KB Output is correct
3 Correct 790 ms 144120 KB Output is correct
4 Correct 807 ms 144132 KB Output is correct
5 Correct 889 ms 144248 KB Output is correct
6 Correct 471 ms 144120 KB Output is correct
7 Correct 793 ms 144200 KB Output is correct
8 Correct 798 ms 144124 KB Output is correct
9 Correct 885 ms 144376 KB Output is correct
10 Correct 472 ms 143992 KB Output is correct
11 Correct 787 ms 144140 KB Output is correct
12 Correct 121 ms 135544 KB Output is correct
13 Correct 3711 ms 190044 KB Output is correct
14 Correct 4881 ms 187564 KB Output is correct
15 Correct 1405 ms 187536 KB Output is correct
16 Correct 6425 ms 206004 KB Output is correct
17 Correct 5194 ms 190756 KB Output is correct
18 Correct 3318 ms 155876 KB Output is correct
19 Correct 856 ms 156652 KB Output is correct
20 Correct 3637 ms 159216 KB Output is correct
21 Correct 3349 ms 157144 KB Output is correct
22 Correct 5254 ms 190252 KB Output is correct
23 Correct 5436 ms 192828 KB Output is correct
24 Correct 7594 ms 191676 KB Output is correct
25 Execution timed out 8034 ms 196908 KB Time limit exceeded
26 Halted 0 ms 0 KB -