oj.uz

답안 #289400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
289400 2020-09-02T15:54:13 Z Haunted_Cpp 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 109028 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 = 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[]) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 65256 KB Output is correct
2 Correct 1161 ms 73276 KB Output is correct
3 Correct 2082 ms 73328 KB Output is correct
4 Correct 2084 ms 73324 KB Output is correct
5 Correct 2337 ms 73464 KB Output is correct
6 Correct 448 ms 73852 KB Output is correct
7 Correct 2150 ms 73968 KB Output is correct
8 Correct 2107 ms 73980 KB Output is correct
9 Correct 2180 ms 74132 KB Output is correct
10 Correct 433 ms 73848 KB Output is correct
11 Correct 1948 ms 74076 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 65152 KB Output is correct
2 Correct 3692 ms 109028 KB Output is correct
3 Execution timed out 8077 ms 108444 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 65256 KB Output is correct
2 Correct 1161 ms 73276 KB Output is correct
3 Correct 2082 ms 73328 KB Output is correct
4 Correct 2084 ms 73324 KB Output is correct
5 Correct 2337 ms 73464 KB Output is correct
6 Correct 448 ms 73852 KB Output is correct
7 Correct 2150 ms 73968 KB Output is correct
8 Correct 2107 ms 73980 KB Output is correct
9 Correct 2180 ms 74132 KB Output is correct
10 Correct 433 ms 73848 KB Output is correct
11 Correct 1948 ms 74076 KB Output is correct
12 Correct 43 ms 65152 KB Output is correct
13 Correct 3692 ms 109028 KB Output is correct
14 Execution timed out 8077 ms 108444 KB Time limit exceeded
15 Halted 0 ms 0 KB -