oj.uz

Submission #400406

# Submission time Handle Problem Language Result Execution time Memory
400406 2021-05-08T00:24:10 Z Haunted_Cpp Factories (JOI14_factories) C++17
100 / 100
 5440 ms 333836 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long i64;
 
const int MAX_N = 500000 + 5;
 
const i64 INF = 1e18;
 
vector<pair<int, int>> g[MAX_N];
vector<pair<int, i64>> par[MAX_N];
 
int sub[MAX_N], del[MAX_N];
i64 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 solve(int node, int p, const int centroid, i64 w) {
  par[node].emplace_back(centroid, w);
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p) {
      solve(to.first, node, centroid, w + to.second);
    }
  }
}
 
void decompose(int node) {
  const int centroid = calc_centroid(node, -1, calc_subtree(node, -1));
  del[centroid] = 1;
  for (auto to : g[centroid]) {
    if (!del[to.first]) {
      solve(to.first, -1, centroid, to.second);
      decompose(to.first);
    }
  }
} 
 
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);
  }
  decompose(0);
  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++) {
    best_way[X[i]] = 0;
    for (auto to : par[X[i]]) {
      best_way[to.first] = min(best_way[to.first], to.second);
    }
  }
  for (int i = 0; i < T; i++) {
    mn = min(mn, best_way[Y[i]]);
    for (auto to : par[Y[i]]) {
      mn = min(mn, best_way[to.first] + to.second);
    }
  }
  for (int i = 0; i < S; i++) {
    best_way[X[i]] = INF;
    for (auto to : par[X[i]]) {
      best_way[to.first] = INF;
    }
  }
  return mn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28212 KB Output is correct
2 Correct 359 ms 46036 KB Output is correct
3 Correct 397 ms 46592 KB Output is correct
4 Correct 398 ms 46532 KB Output is correct
5 Correct 423 ms 47164 KB Output is correct
6 Correct 292 ms 45532 KB Output is correct
7 Correct 395 ms 46636 KB Output is correct
8 Correct 403 ms 46532 KB Output is correct
9 Correct 426 ms 46968 KB Output is correct
10 Correct 300 ms 45508 KB Output is correct
11 Correct 442 ms 46584 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27852 KB Output is correct
2 Correct 2362 ms 198584 KB Output is correct
3 Correct 3459 ms 242080 KB Output is correct
4 Correct 900 ms 97736 KB Output is correct
5 Correct 4587 ms 333836 KB Output is correct
6 Correct 3664 ms 243520 KB Output is correct
7 Correct 1152 ms 84184 KB Output is correct
8 Correct 496 ms 61040 KB Output is correct
9 Correct 1230 ms 87988 KB Output is correct
10 Correct 1235 ms 85648 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28212 KB Output is correct
2 Correct 359 ms 46036 KB Output is correct
3 Correct 397 ms 46592 KB Output is correct
4 Correct 398 ms 46532 KB Output is correct
5 Correct 423 ms 47164 KB Output is correct
6 Correct 292 ms 45532 KB Output is correct
7 Correct 395 ms 46636 KB Output is correct
8 Correct 403 ms 46532 KB Output is correct
9 Correct 426 ms 46968 KB Output is correct
10 Correct 300 ms 45508 KB Output is correct
11 Correct 442 ms 46584 KB Output is correct
12 Correct 17 ms 27852 KB Output is correct
13 Correct 2362 ms 198584 KB Output is correct
14 Correct 3459 ms 242080 KB Output is correct
15 Correct 900 ms 97736 KB Output is correct
16 Correct 4587 ms 333836 KB Output is correct
17 Correct 3664 ms 243520 KB Output is correct
18 Correct 1152 ms 84184 KB Output is correct
19 Correct 496 ms 61040 KB Output is correct
20 Correct 1230 ms 87988 KB Output is correct
21 Correct 1235 ms 85648 KB Output is correct
22 Correct 2959 ms 183660 KB Output is correct
23 Correct 3070 ms 190188 KB Output is correct
24 Correct 4415 ms 230384 KB Output is correct
25 Correct 4414 ms 234244 KB Output is correct
26 Correct 4238 ms 231288 KB Output is correct
27 Correct 5440 ms 318212 KB Output is correct
28 Correct 1345 ms 88040 KB Output is correct
29 Correct 4323 ms 230592 KB Output is correct
30 Correct 4284 ms 229660 KB Output is correct
31 Correct 4265 ms 230272 KB Output is correct
32 Correct 1396 ms 88900 KB Output is correct
33 Correct 558 ms 61320 KB Output is correct
34 Correct 984 ms 74136 KB Output is correct
35 Correct 957 ms 75188 KB Output is correct
36 Correct 1219 ms 82556 KB Output is correct
37 Correct 1200 ms 82648 KB Output is correct