oj.uz

Submission #289529

# Submission time Handle Problem Language Result Execution time Memory
289529 2020-09-02T17:43:35 Z Haunted_Cpp Factories (JOI14_factories) C++17
33 / 100
 8000 ms 204100 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize ("Ofast")
 
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 636 ms 144028 KB Output is correct
3 Correct 835 ms 143948 KB Output is correct
4 Correct 795 ms 143992 KB Output is correct
5 Correct 828 ms 144248 KB Output is correct
6 Correct 447 ms 143992 KB Output is correct
7 Correct 826 ms 143992 KB Output is correct
8 Correct 800 ms 144124 KB Output is correct
9 Correct 818 ms 144120 KB Output is correct
10 Correct 442 ms 143992 KB Output is correct
11 Correct 819 ms 144120 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 135544 KB Output is correct
2 Correct 3235 ms 186688 KB Output is correct
3 Correct 4411 ms 187248 KB Output is correct
4 Correct 1291 ms 187348 KB Output is correct
5 Correct 6301 ms 204100 KB Output is correct
6 Correct 4754 ms 188920 KB Output is correct
7 Correct 2991 ms 154060 KB Output is correct
8 Correct 796 ms 155040 KB Output is correct
9 Correct 2963 ms 157072 KB Output is correct
10 Correct 2789 ms 155512 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 636 ms 144028 KB Output is correct
3 Correct 835 ms 143948 KB Output is correct
4 Correct 795 ms 143992 KB Output is correct
5 Correct 828 ms 144248 KB Output is correct
6 Correct 447 ms 143992 KB Output is correct
7 Correct 826 ms 143992 KB Output is correct
8 Correct 800 ms 144124 KB Output is correct
9 Correct 818 ms 144120 KB Output is correct
10 Correct 442 ms 143992 KB Output is correct
11 Correct 819 ms 144120 KB Output is correct
12 Correct 119 ms 135544 KB Output is correct
13 Correct 3235 ms 186688 KB Output is correct
14 Correct 4411 ms 187248 KB Output is correct
15 Correct 1291 ms 187348 KB Output is correct
16 Correct 6301 ms 204100 KB Output is correct
17 Correct 4754 ms 188920 KB Output is correct
18 Correct 2991 ms 154060 KB Output is correct
19 Correct 796 ms 155040 KB Output is correct
20 Correct 2963 ms 157072 KB Output is correct
21 Correct 2789 ms 155512 KB Output is correct
22 Correct 4481 ms 188156 KB Output is correct
23 Correct 4786 ms 190492 KB Output is correct
24 Correct 6982 ms 189376 KB Output is correct
25 Correct 6777 ms 192644 KB Output is correct
26 Correct 7988 ms 189408 KB Output is correct
27 Execution timed out 8115 ms 201728 KB Time limit exceeded
28 Halted 0 ms 0 KB -