oj.uz

Submission #289470

# Submission time Handle Problem Language Result Execution time Memory
289470 2020-09-02T16:46:32 Z Haunted_Cpp Factories (JOI14_factories) C++17
15 / 100
 3250 ms 243552 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 = 25 + 5;
const i64 INF = 1e18;

vector<pair<int, int>> g[MAX_N];

int dp[MAX_N][MAX_K], table[5 * MAX_N][MAX_K];
int sub[MAX_N], del[MAX_N], par[MAX_N], in[MAX_N], depth[MAX_N], L[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);
  dp[node][0] = p;
  for (auto to : g[node]) {
    if (to.first != p) {
      depth[to.first] = depth[node] + 1;
      d[to.first] = d[node] + to.second;
      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 (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 = best_way[node];
  node = par[node];
  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);
  }
  memset(dp, -1, sizeof(dp));
  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 51 ms 75128 KB Output is correct
2 Correct 739 ms 84472 KB Output is correct
3 Correct 917 ms 84632 KB Output is correct
4 Correct 818 ms 84600 KB Output is correct
5 Correct 825 ms 84680 KB Output is correct
6 Correct 413 ms 84600 KB Output is correct
7 Correct 778 ms 84600 KB Output is correct
8 Correct 808 ms 84596 KB Output is correct
9 Correct 812 ms 84728 KB Output is correct
10 Correct 404 ms 84476 KB Output is correct
11 Correct 811 ms 84640 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 75000 KB Output is correct
2 Incorrect 3250 ms 243552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 75128 KB Output is correct
2 Correct 739 ms 84472 KB Output is correct
3 Correct 917 ms 84632 KB Output is correct
4 Correct 818 ms 84600 KB Output is correct
5 Correct 825 ms 84680 KB Output is correct
6 Correct 413 ms 84600 KB Output is correct
7 Correct 778 ms 84600 KB Output is correct
8 Correct 808 ms 84596 KB Output is correct
9 Correct 812 ms 84728 KB Output is correct
10 Correct 404 ms 84476 KB Output is correct
11 Correct 811 ms 84640 KB Output is correct
12 Correct 43 ms 75000 KB Output is correct
13 Incorrect 3250 ms 243552 KB Output isn't correct
14 Halted 0 ms 0 KB -