oj.uz

Submission #290421

# Submission time Handle Problem Language Result Execution time Memory
290421 2020-09-03T18:37:17 Z Haunted_Cpp Factories (JOI14_factories) C++17
100 / 100
 5431 ms 308748 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 26 ms 28160 KB Output is correct
2 Correct 380 ms 42616 KB Output is correct
3 Correct 422 ms 42940 KB Output is correct
4 Correct 413 ms 43000 KB Output is correct
5 Correct 429 ms 43384 KB Output is correct
6 Correct 314 ms 42104 KB Output is correct
7 Correct 432 ms 43896 KB Output is correct
8 Correct 408 ms 43896 KB Output is correct
9 Correct 429 ms 44316 KB Output is correct
10 Correct 318 ms 43004 KB Output is correct
11 Correct 399 ms 43896 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27904 KB Output is correct
2 Correct 2700 ms 180344 KB Output is correct
3 Correct 3941 ms 229540 KB Output is correct
4 Correct 1047 ms 79724 KB Output is correct
5 Correct 5082 ms 308748 KB Output is correct
6 Correct 4085 ms 224376 KB Output is correct
7 Correct 1360 ms 77508 KB Output is correct
8 Correct 539 ms 54272 KB Output is correct
9 Correct 1421 ms 81148 KB Output is correct
10 Correct 1397 ms 78744 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28160 KB Output is correct
2 Correct 380 ms 42616 KB Output is correct
3 Correct 422 ms 42940 KB Output is correct
4 Correct 413 ms 43000 KB Output is correct
5 Correct 429 ms 43384 KB Output is correct
6 Correct 314 ms 42104 KB Output is correct
7 Correct 432 ms 43896 KB Output is correct
8 Correct 408 ms 43896 KB Output is correct
9 Correct 429 ms 44316 KB Output is correct
10 Correct 318 ms 43004 KB Output is correct
11 Correct 399 ms 43896 KB Output is correct
12 Correct 20 ms 27904 KB Output is correct
13 Correct 2700 ms 180344 KB Output is correct
14 Correct 3941 ms 229540 KB Output is correct
15 Correct 1047 ms 79724 KB Output is correct
16 Correct 5082 ms 308748 KB Output is correct
17 Correct 4085 ms 224376 KB Output is correct
18 Correct 1360 ms 77508 KB Output is correct
19 Correct 539 ms 54272 KB Output is correct
20 Correct 1421 ms 81148 KB Output is correct
21 Correct 1397 ms 78744 KB Output is correct
22 Correct 3196 ms 187468 KB Output is correct
23 Correct 3194 ms 192640 KB Output is correct
24 Correct 4603 ms 233148 KB Output is correct
25 Correct 4525 ms 235160 KB Output is correct
26 Correct 4436 ms 233692 KB Output is correct
27 Correct 5431 ms 308472 KB Output is correct
28 Correct 1408 ms 83744 KB Output is correct
29 Correct 4447 ms 225332 KB Output is correct
30 Correct 4402 ms 224956 KB Output is correct
31 Correct 4424 ms 225308 KB Output is correct
32 Correct 1508 ms 77280 KB Output is correct
33 Correct 633 ms 50288 KB Output is correct
34 Correct 1032 ms 63352 KB Output is correct
35 Correct 1020 ms 64492 KB Output is correct
36 Correct 1264 ms 71544 KB Output is correct
37 Correct 1259 ms 71672 KB Output is correct