oj.uz

Submission #728161

# Submission time Handle Problem Language Result Execution time Memory
728161 2023-04-22T03:33:27 Z jampm Factories (JOI14_factories) C++17
100 / 100
 4488 ms 208704 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int Mxn = 5e5 + 1;
const ll INF = 1e17;
const int LOGN = 19;


vector<vector<pair<int, ll>>> Adj;
ll best[Mxn];
bool vis[Mxn];
int tree[LOGN][Mxn];
ll dist[LOGN][Mxn];
int Sz[Mxn];

int get_size(int node, int parent) {
  Sz[node] = 1;
  for (auto [child, w] : Adj[node]) {
    if (child == parent || vis[child]) continue;
    Sz[node] += get_size(child, node);
  }
  return Sz[node];
}

int get_centroid(int node, int parent, int S) {
  for (auto [child, w] : Adj[node]) {
    if (child == parent || vis[child]) continue;
    if (2*Sz[child] >= S) return get_centroid(child, node, S);
  }
  return node;
}

void dfs(int node, int parent, int depth, ll W = 0) {
  dist[depth][node] = dist[depth][parent] + W;
  tree[depth][node] = tree[depth][parent];
  for (auto [child, w] : Adj[node]) {
    if (child == parent || vis[child]) continue;
    dfs(child, node, depth, w);
  }
}

void centroid_decomp(int node = 1, int depth = 0) {
  int c = get_centroid(node, node, get_size(node, node));
  dist[depth][c] = 0; tree[depth][c] = c;
  dfs(c, c, depth); vis[c] = true;

  for (auto [child, w] : Adj[c]) {
    if (!vis[child]) centroid_decomp(child, depth + 1);
  }
}

void clear(int node) {
  for (int i = 0; i < LOGN; i++) {
    if (tree[i][node] == -1) break;
    best[tree[i][node]] = INF;
  }
}
void add(int node) {
  for (int i = 0; i < LOGN; i++) {
    if (tree[i][node] == -1) break;
    best[tree[i][node]] = min(best[tree[i][node]], dist[i][node]);
  }
}

ll query(int node, ll ans = INF) {
  for (int i = 0; i < LOGN; i++) {
    if (tree[i][node] == -1) break;
    ans = min(ans, dist[i][node] + best[tree[i][node]]);
  }
  return ans;
}

void Init(int N, int A[], int B[], int D[]) {
  Adj.resize(N + 1, {});
  for (int i = 0; i < N - 1; i++) {
    Adj[A[i]].push_back({B[i], (ll)D[i]});
    Adj[B[i]].push_back({A[i], (ll)D[i]});
  }
  for (int i = 0; i < N; i++) best[i] = INF;
  memset(tree, -1, sizeof(tree));
  centroid_decomp();
  for (int i = 0; i < N; i++) best[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
  ll ans = INF;
  for (int i = 0; i < S; i++) add(X[i]);
  for (int i = 0; i < T; i++) ans = min(ans, query(Y[i]));
  for (int i = 0; i < S; i++) clear(X[i]);
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37844 KB Output is correct
2 Correct 299 ms 46492 KB Output is correct
3 Correct 315 ms 46636 KB Output is correct
4 Correct 316 ms 46652 KB Output is correct
5 Correct 327 ms 46864 KB Output is correct
6 Correct 215 ms 46028 KB Output is correct
7 Correct 323 ms 46676 KB Output is correct
8 Correct 337 ms 46576 KB Output is correct
9 Correct 334 ms 46740 KB Output is correct
10 Correct 225 ms 46112 KB Output is correct
11 Correct 325 ms 46616 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37716 KB Output is correct
2 Correct 1794 ms 153004 KB Output is correct
3 Correct 2733 ms 170984 KB Output is correct
4 Correct 610 ms 99784 KB Output is correct
5 Correct 3580 ms 196564 KB Output is correct
6 Correct 2843 ms 172780 KB Output is correct
7 Correct 1152 ms 76512 KB Output is correct
8 Correct 390 ms 64644 KB Output is correct
9 Correct 1344 ms 81676 KB Output is correct
10 Correct 1136 ms 77652 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37844 KB Output is correct
2 Correct 299 ms 46492 KB Output is correct
3 Correct 315 ms 46636 KB Output is correct
4 Correct 316 ms 46652 KB Output is correct
5 Correct 327 ms 46864 KB Output is correct
6 Correct 215 ms 46028 KB Output is correct
7 Correct 323 ms 46676 KB Output is correct
8 Correct 337 ms 46576 KB Output is correct
9 Correct 334 ms 46740 KB Output is correct
10 Correct 225 ms 46112 KB Output is correct
11 Correct 325 ms 46616 KB Output is correct
12 Correct 19 ms 37716 KB Output is correct
13 Correct 1794 ms 153004 KB Output is correct
14 Correct 2733 ms 170984 KB Output is correct
15 Correct 610 ms 99784 KB Output is correct
16 Correct 3580 ms 196564 KB Output is correct
17 Correct 2843 ms 172780 KB Output is correct
18 Correct 1152 ms 76512 KB Output is correct
19 Correct 390 ms 64644 KB Output is correct
20 Correct 1344 ms 81676 KB Output is correct
21 Correct 1136 ms 77652 KB Output is correct
22 Correct 2409 ms 153584 KB Output is correct
23 Correct 2392 ms 162984 KB Output is correct
24 Correct 3671 ms 179420 KB Output is correct
25 Correct 3601 ms 181052 KB Output is correct
26 Correct 3336 ms 179272 KB Output is correct
27 Correct 4488 ms 208704 KB Output is correct
28 Correct 816 ms 108632 KB Output is correct
29 Correct 3464 ms 177880 KB Output is correct
30 Correct 3413 ms 178844 KB Output is correct
31 Correct 3469 ms 179000 KB Output is correct
32 Correct 1308 ms 82792 KB Output is correct
33 Correct 335 ms 65032 KB Output is correct
34 Correct 767 ms 71816 KB Output is correct
35 Correct 840 ms 71976 KB Output is correct
36 Correct 1153 ms 75272 KB Output is correct
37 Correct 1120 ms 75524 KB Output is correct