oj.uz

Submission #289415

# Submission time Handle Problem Language Result Execution time Memory
289415 2020-09-02T16:10:00 Z Haunted_Cpp Factories (JOI14_factories) C++17
15 / 100
 8000 ms 108436 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 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 = 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);
  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;
  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

# Verdict Execution time Memory Grader output
1 Correct 64 ms 65528 KB Output is correct
2 Correct 1182 ms 73748 KB Output is correct
3 Correct 2003 ms 73860 KB Output is correct
4 Correct 1890 ms 73856 KB Output is correct
5 Correct 2124 ms 73976 KB Output is correct
6 Correct 451 ms 73336 KB Output is correct
7 Correct 1961 ms 73672 KB Output is correct
8 Correct 1982 ms 73432 KB Output is correct
9 Correct 2151 ms 73584 KB Output is correct
10 Correct 477 ms 73328 KB Output is correct
11 Correct 1990 ms 73292 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65016 KB Output is correct
2 Correct 3693 ms 108192 KB Output is correct
3 Execution timed out 8061 ms 108436 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 65528 KB Output is correct
2 Correct 1182 ms 73748 KB Output is correct
3 Correct 2003 ms 73860 KB Output is correct
4 Correct 1890 ms 73856 KB Output is correct
5 Correct 2124 ms 73976 KB Output is correct
6 Correct 451 ms 73336 KB Output is correct
7 Correct 1961 ms 73672 KB Output is correct
8 Correct 1982 ms 73432 KB Output is correct
9 Correct 2151 ms 73584 KB Output is correct
10 Correct 477 ms 73328 KB Output is correct
11 Correct 1990 ms 73292 KB Output is correct
12 Correct 39 ms 65016 KB Output is correct
13 Correct 3693 ms 108192 KB Output is correct
14 Execution timed out 8061 ms 108436 KB Time limit exceeded
15 Halted 0 ms 0 KB -