oj.uz

답안 #289520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
289520 2020-09-02T17:36:26 Z Haunted_Cpp 공장들 (JOI14_factories) C++17
15 / 100
 3342 ms 186808 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 = 19;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 135672 KB Output is correct
2 Correct 650 ms 143992 KB Output is correct
3 Correct 836 ms 143864 KB Output is correct
4 Correct 793 ms 143940 KB Output is correct
5 Correct 828 ms 144120 KB Output is correct
6 Correct 452 ms 143992 KB Output is correct
7 Correct 827 ms 143864 KB Output is correct
8 Correct 810 ms 144120 KB Output is correct
9 Correct 832 ms 144248 KB Output is correct
10 Correct 456 ms 143992 KB Output is correct
11 Correct 827 ms 143992 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 135672 KB Output is correct
2 Incorrect 3342 ms 186808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 135672 KB Output is correct
2 Correct 650 ms 143992 KB Output is correct
3 Correct 836 ms 143864 KB Output is correct
4 Correct 793 ms 143940 KB Output is correct
5 Correct 828 ms 144120 KB Output is correct
6 Correct 452 ms 143992 KB Output is correct
7 Correct 827 ms 143864 KB Output is correct
8 Correct 810 ms 144120 KB Output is correct
9 Correct 832 ms 144248 KB Output is correct
10 Correct 456 ms 143992 KB Output is correct
11 Correct 827 ms 143992 KB Output is correct
12 Correct 133 ms 135672 KB Output is correct
13 Incorrect 3342 ms 186808 KB Output isn't correct
14 Halted 0 ms 0 KB -