oj.uz

Submission #289512

# Submission time Handle Problem Language Result Execution time Memory
289512 2020-09-02T17:28:41 Z Haunted_Cpp Factories (JOI14_factories) C++17
33 / 100
 8000 ms 222376 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 + 5;
const i64 INF = 1e18;
 
vector<pair<int, int>> g[MAX_N];
 
int sub[MAX_N], del[MAX_N], par[MAX_N], in[MAX_N], 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]];
      assert(i + (1 << (j - 1)) >= 0);
      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 - (1 << k) + 1][k]];
  return (H1 < H2 ? table[st][k] : table[et - (1 << 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);
  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 143 ms 151548 KB Output is correct
2 Correct 708 ms 162552 KB Output is correct
3 Correct 821 ms 169080 KB Output is correct
4 Correct 820 ms 169084 KB Output is correct
5 Correct 896 ms 169336 KB Output is correct
6 Correct 484 ms 169080 KB Output is correct
7 Correct 807 ms 169068 KB Output is correct
8 Correct 812 ms 169080 KB Output is correct
9 Correct 888 ms 169208 KB Output is correct
10 Correct 481 ms 169080 KB Output is correct
11 Correct 808 ms 169080 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 151308 KB Output is correct
2 Correct 3789 ms 207368 KB Output is correct
3 Correct 5038 ms 203280 KB Output is correct
4 Correct 1442 ms 204888 KB Output is correct
5 Correct 6701 ms 222376 KB Output is correct
6 Correct 5384 ms 206812 KB Output is correct
7 Correct 3484 ms 170712 KB Output is correct
8 Correct 913 ms 171240 KB Output is correct
9 Correct 3757 ms 173524 KB Output is correct
10 Correct 3423 ms 172012 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 151548 KB Output is correct
2 Correct 708 ms 162552 KB Output is correct
3 Correct 821 ms 169080 KB Output is correct
4 Correct 820 ms 169084 KB Output is correct
5 Correct 896 ms 169336 KB Output is correct
6 Correct 484 ms 169080 KB Output is correct
7 Correct 807 ms 169068 KB Output is correct
8 Correct 812 ms 169080 KB Output is correct
9 Correct 888 ms 169208 KB Output is correct
10 Correct 481 ms 169080 KB Output is correct
11 Correct 808 ms 169080 KB Output is correct
12 Correct 133 ms 151308 KB Output is correct
13 Correct 3789 ms 207368 KB Output is correct
14 Correct 5038 ms 203280 KB Output is correct
15 Correct 1442 ms 204888 KB Output is correct
16 Correct 6701 ms 222376 KB Output is correct
17 Correct 5384 ms 206812 KB Output is correct
18 Correct 3484 ms 170712 KB Output is correct
19 Correct 913 ms 171240 KB Output is correct
20 Correct 3757 ms 173524 KB Output is correct
21 Correct 3423 ms 172012 KB Output is correct
22 Correct 5420 ms 204752 KB Output is correct
23 Correct 5589 ms 206948 KB Output is correct
24 Execution timed out 8069 ms 205836 KB Time limit exceeded
25 Halted 0 ms 0 KB -