oj.uz

Submission #289507

# Submission time Handle Problem Language Result Execution time Memory
289507 2020-09-02T17:23:40 Z Haunted_Cpp Factories (JOI14_factories) C++17
33 / 100
 8000 ms 385248 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long i64;
 
const int MAX_N = 1e6 + 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[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 265 ms 302200 KB Output is correct
2 Correct 847 ms 311584 KB Output is correct
3 Correct 995 ms 311776 KB Output is correct
4 Correct 964 ms 311624 KB Output is correct
5 Correct 1027 ms 311800 KB Output is correct
6 Correct 633 ms 311604 KB Output is correct
7 Correct 956 ms 311672 KB Output is correct
8 Correct 969 ms 311600 KB Output is correct
9 Correct 1028 ms 311800 KB Output is correct
10 Correct 678 ms 311680 KB Output is correct
11 Correct 964 ms 311652 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 301944 KB Output is correct
2 Correct 4200 ms 355428 KB Output is correct
3 Correct 5610 ms 353652 KB Output is correct
4 Correct 1743 ms 371792 KB Output is correct
5 Correct 7145 ms 385248 KB Output is correct
6 Correct 5862 ms 370152 KB Output is correct
7 Correct 3812 ms 334140 KB Output is correct
8 Correct 1117 ms 335212 KB Output is correct
9 Correct 4316 ms 337252 KB Output is correct
10 Correct 3773 ms 335672 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 302200 KB Output is correct
2 Correct 847 ms 311584 KB Output is correct
3 Correct 995 ms 311776 KB Output is correct
4 Correct 964 ms 311624 KB Output is correct
5 Correct 1027 ms 311800 KB Output is correct
6 Correct 633 ms 311604 KB Output is correct
7 Correct 956 ms 311672 KB Output is correct
8 Correct 969 ms 311600 KB Output is correct
9 Correct 1028 ms 311800 KB Output is correct
10 Correct 678 ms 311680 KB Output is correct
11 Correct 964 ms 311652 KB Output is correct
12 Correct 259 ms 301944 KB Output is correct
13 Correct 4200 ms 355428 KB Output is correct
14 Correct 5610 ms 353652 KB Output is correct
15 Correct 1743 ms 371792 KB Output is correct
16 Correct 7145 ms 385248 KB Output is correct
17 Correct 5862 ms 370152 KB Output is correct
18 Correct 3812 ms 334140 KB Output is correct
19 Correct 1117 ms 335212 KB Output is correct
20 Correct 4316 ms 337252 KB Output is correct
21 Correct 3773 ms 335672 KB Output is correct
22 Correct 5646 ms 360120 KB Output is correct
23 Correct 5809 ms 362420 KB Output is correct
24 Correct 7987 ms 361472 KB Output is correct
25 Execution timed out 8060 ms 364532 KB Time limit exceeded
26 Halted 0 ms 0 KB -