oj.uz

Submission #728157

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


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 10 ms 7508 KB Output is correct
2 Correct 280 ms 21948 KB Output is correct
3 Correct 311 ms 22156 KB Output is correct
4 Correct 308 ms 22008 KB Output is correct
5 Correct 331 ms 22204 KB Output is correct
6 Correct 209 ms 21508 KB Output is correct
7 Correct 314 ms 22064 KB Output is correct
8 Correct 314 ms 22064 KB Output is correct
9 Correct 340 ms 22256 KB Output is correct
10 Correct 239 ms 21576 KB Output is correct
11 Correct 338 ms 21944 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7124 KB Output is correct
2 Runtime error 482 ms 120144 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7508 KB Output is correct
2 Correct 280 ms 21948 KB Output is correct
3 Correct 311 ms 22156 KB Output is correct
4 Correct 308 ms 22008 KB Output is correct
5 Correct 331 ms 22204 KB Output is correct
6 Correct 209 ms 21508 KB Output is correct
7 Correct 314 ms 22064 KB Output is correct
8 Correct 314 ms 22064 KB Output is correct
9 Correct 340 ms 22256 KB Output is correct
10 Correct 239 ms 21576 KB Output is correct
11 Correct 338 ms 21944 KB Output is correct
12 Correct 4 ms 7124 KB Output is correct
13 Runtime error 482 ms 120144 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -