oj.uz

Submission #289384

# Submission time Handle Problem Language Result Execution time Memory
289384 2020-09-02T15:47:00 Z Haunted_Cpp Factories (JOI14_factories) C++17
15 / 100
 8000 ms 126052 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;

const int MAX_N = 5e5 + 5;
const int MAX_K = 20 + 5;
const i64 INF = 1e18;

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

int dp[MAX_N][MAX_K];
int sub[MAX_N], del[MAX_N], par[MAX_N], h[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);
    }
  }
}

void prep(int node, int p) {
  dp[node][0] = p;
  for (auto to : g[node]) {
    if (to.first != p) {
      d[to.first] = d[node] + to.second;
      h[to.first] = h[node] + 1;
      prep(to.first, node);
    }
  }
}

int kth(int u, int diff) {
  assert(diff >= 0);
  for (int i = MAX_K - 1; ~i; i--) {
    if ((diff >> i) & 1) {
      u = dp[u][i];
    }
  }
  return u;
}

int lca(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  u = kth(u, h[u] - h[v]);
  if (u == v) return u;
  for (int i = MAX_K - 1; ~i; i--) {
    if (dp[u][i] != dp[v][i]) {
      u = dp[u][i];
      v = dp[v][i];
    }
  }
  return dp[u][0];
}

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);
  }
  memset(dp, -1, sizeof(dp));
  prep(0, -1);
  for (int j = 1; j < MAX_K; j++) {
    for (int i = 0; i < N; i++) {
      if (~dp[i][j - 1]) {
        dp[i][j] = dp[dp[i][j - 1]][j - 1];
      }
    }
  }
  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 81 ms 65400 KB Output is correct
2 Correct 1255 ms 73464 KB Output is correct
3 Correct 2131 ms 82908 KB Output is correct
4 Correct 2029 ms 82880 KB Output is correct
5 Correct 2280 ms 83032 KB Output is correct
6 Correct 490 ms 82844 KB Output is correct
7 Correct 1990 ms 82884 KB Output is correct
8 Correct 2317 ms 82760 KB Output is correct
9 Correct 2180 ms 83036 KB Output is correct
10 Correct 503 ms 82740 KB Output is correct
11 Correct 2008 ms 82880 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 65144 KB Output is correct
2 Correct 3881 ms 108288 KB Output is correct
3 Execution timed out 8051 ms 126052 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 65400 KB Output is correct
2 Correct 1255 ms 73464 KB Output is correct
3 Correct 2131 ms 82908 KB Output is correct
4 Correct 2029 ms 82880 KB Output is correct
5 Correct 2280 ms 83032 KB Output is correct
6 Correct 490 ms 82844 KB Output is correct
7 Correct 1990 ms 82884 KB Output is correct
8 Correct 2317 ms 82760 KB Output is correct
9 Correct 2180 ms 83036 KB Output is correct
10 Correct 503 ms 82740 KB Output is correct
11 Correct 2008 ms 82880 KB Output is correct
12 Correct 40 ms 65144 KB Output is correct
13 Correct 3881 ms 108288 KB Output is correct
14 Execution timed out 8051 ms 126052 KB Time limit exceeded
15 Halted 0 ms 0 KB -