oj.uz

Submission #289521

# Submission time Handle Problem Language Result Execution time Memory
289521 2020-09-02T17:37:27 Z Haunted_Cpp Factories (JOI14_factories) C++17
33 / 100
 8000 ms 209448 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 = 20;
const i64 INF = 1e18;
 
int Time = 0;
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] = Time++;
  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);
      Time++;
    }
  }
}
 
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]);
    }
  }
}
 
inline int lca(int u, int v) {
  if (u == v) return u;
  if (in[u] > in[v]) {
    swap(u, v);
  }
  const int st = in[u];
  const int et = in[v];
  const int k = L[(et - st + 1)];
  return (depth[table[st][k]] < depth[table[et - pw[k] + 1][k]] ? 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;
  if (S > T) {
    swap(S, T);
    swap(X, Y);
  }
  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 128 ms 135672 KB Output is correct
2 Correct 644 ms 144060 KB Output is correct
3 Correct 843 ms 144120 KB Output is correct
4 Correct 785 ms 144248 KB Output is correct
5 Correct 825 ms 144248 KB Output is correct
6 Correct 448 ms 143992 KB Output is correct
7 Correct 816 ms 143928 KB Output is correct
8 Correct 798 ms 144000 KB Output is correct
9 Correct 836 ms 144292 KB Output is correct
10 Correct 446 ms 143996 KB Output is correct
11 Correct 820 ms 143864 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 135544 KB Output is correct
2 Correct 3346 ms 186564 KB Output is correct
3 Correct 4574 ms 187232 KB Output is correct
4 Correct 1388 ms 187352 KB Output is correct
5 Correct 5936 ms 204004 KB Output is correct
6 Correct 4720 ms 188720 KB Output is correct
7 Correct 2982 ms 153968 KB Output is correct
8 Correct 808 ms 154988 KB Output is correct
9 Correct 3102 ms 156784 KB Output is correct
10 Correct 2954 ms 155408 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 135672 KB Output is correct
2 Correct 644 ms 144060 KB Output is correct
3 Correct 843 ms 144120 KB Output is correct
4 Correct 785 ms 144248 KB Output is correct
5 Correct 825 ms 144248 KB Output is correct
6 Correct 448 ms 143992 KB Output is correct
7 Correct 816 ms 143928 KB Output is correct
8 Correct 798 ms 144000 KB Output is correct
9 Correct 836 ms 144292 KB Output is correct
10 Correct 446 ms 143996 KB Output is correct
11 Correct 820 ms 143864 KB Output is correct
12 Correct 123 ms 135544 KB Output is correct
13 Correct 3346 ms 186564 KB Output is correct
14 Correct 4574 ms 187232 KB Output is correct
15 Correct 1388 ms 187352 KB Output is correct
16 Correct 5936 ms 204004 KB Output is correct
17 Correct 4720 ms 188720 KB Output is correct
18 Correct 2982 ms 153968 KB Output is correct
19 Correct 808 ms 154988 KB Output is correct
20 Correct 3102 ms 156784 KB Output is correct
21 Correct 2954 ms 155408 KB Output is correct
22 Correct 4729 ms 188216 KB Output is correct
23 Correct 4720 ms 190600 KB Output is correct
24 Correct 6741 ms 189436 KB Output is correct
25 Correct 7008 ms 192632 KB Output is correct
26 Correct 7239 ms 194944 KB Output is correct
27 Execution timed out 8106 ms 209448 KB Time limit exceeded
28 Halted 0 ms 0 KB -