oj.uz

Submission #529248

# Submission time Handle Problem Language Result Execution time Memory
529248 2022-02-22T14:26:28 Z Alex_tz307 Factories (JOI14_factories) C++17
100 / 100
 5014 ms 194928 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

const int kN = 5e5;
const int kLog = 18;
const int64_t INF = 2e18L;
int M, qIndex, tin[1 + kN], tour[2 * kN], depth[1 + kN], sz[1 + kN], p[1 + kN], curr[1 + kN], lg2[2 * kN], rmq[2 * kN][1 + kLog + 1];
int64_t dp[1 + kN], best[1 + kN];
vector<pair<int, int>> g[1 + kN];
bitset<1 + kN> vis;
vector<int> modified;

void precalc() {
  for (int i = 2; i < 2 * kN; ++i) {
    lg2[i] = lg2[i / 2] + 1;
  }
}

void minSelf(int64_t &x, int64_t y) {
  if (y < x) {
    x = y;
  }
}

void dfs(int u, int par) {
  depth[u] = depth[par] + 1;
  tin[u] = ++M;
  tour[M] = u;
  for (auto it : g[u]) {
    int v, w;
    tie(v, w) = it;
    if (v != par) {
      dp[v] = dp[u] + w;
      dfs(v, u);
      tour[++M] = u;
    }
  }
}

void buildRmq() {
  for (int i = 1; i <= M; ++i) {
    rmq[i][0] = tour[i];
  }
  for (int j = 1; (1 << j) <= M; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= M; ++i) {
      rmq[i][j] = rmq[i][j - 1];
      if (depth[rmq[i + (1 << (j - 1))][j - 1]] < depth[rmq[i][j]]) {
        rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
      }
    }
  }
}

void findSize(int u, int par) {
  sz[u] = 1;
  for (auto it : g[u]) {
    int v = it.first;
    if (!vis[v] && v != par) {
      findSize(v, u);
      sz[u] += sz[v];
    }
  }
}

int findCentroid(int u, int par, int n) {
  for (auto it : g[u]) {
    int v = it.first;
    if (!vis[v] && v != par && sz[v] > n / 2) {
      return findCentroid(v, u, n);
    }
  }
  return u;
}

void build(int u, int par) {
  findSize(u, 0);
  int c = findCentroid(u, 0, sz[u]);
  vis[c] = true;
  p[c] = par;
  for (auto it : g[c]) {
    int v = it.first;
    if (!vis[v]) {
      build(v, c);
    }
  }
}

int getLca(int u, int v) {
  if (tin[v] < tin[u]) {
    swap(u, v);
  }
  int diff = tin[v] - tin[u] + 1;
  int k = lg2[diff];
  int shift = diff - (1 << k);
  if (depth[rmq[tin[u]][k]] < depth[rmq[tin[u] + shift][k]]) {
    return rmq[tin[u]][k];
  }
  return rmq[tin[u] + shift][k];
}

int64_t getDist(int u, int v, int lca) {
  return dp[u] + dp[v] - 2 * dp[lca];
}

void update(int u) {
  best[u] = 0;
  int v = u;
  while (v) {
    if (curr[v] != qIndex) {
      curr[v] = qIndex;
      modified.emplace_back(v);
    }
    minSelf(best[v], getDist(u, v, getLca(u, v)));
    v = p[v];
  }
}

int64_t query(int u) {
  int64_t ans = INF;
  int v = u;
  while (v) {
    minSelf(ans, best[v] + getDist(u, v, getLca(u, v)));
    v = p[v];
  }
  return ans;
}

void Init(int n, int a[], int b[], int d[]) {
  precalc();
  for (int i = 0; i <= n - 2; ++i) {
    a[i] += 1;
    b[i] += 1;
    g[a[i]].emplace_back(b[i], d[i]);
    g[b[i]].emplace_back(a[i], d[i]);
  }
  dfs(1, 0);
  buildRmq();
  build(1, 0);
  for (int v = 1; v <= n; ++v) {
    best[v] = INF;
  }
}

long long Query(int n, int x[], int m, int y[]) {
  qIndex += 1;
  modified.clear();
  for (int i = 0; i < n; ++i) {
    x[i] += 1;
    update(x[i]);
  }
  int64_t ans = INF;
  for (int i = 0; i < m; ++i) {
    y[i] += 1;
    minSelf(ans, query(y[i]));
  }
  for (int v : modified) {
    best[v] = INF;
  }
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16332 KB Output is correct
2 Correct 352 ms 25252 KB Output is correct
3 Correct 436 ms 25368 KB Output is correct
4 Correct 407 ms 25264 KB Output is correct
5 Correct 500 ms 25472 KB Output is correct
6 Correct 224 ms 25220 KB Output is correct
7 Correct 440 ms 25280 KB Output is correct
8 Correct 437 ms 25272 KB Output is correct
9 Correct 509 ms 25544 KB Output is correct
10 Correct 227 ms 25248 KB Output is correct
11 Correct 426 ms 25224 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16204 KB Output is correct
2 Correct 2016 ms 147316 KB Output is correct
3 Correct 2760 ms 148960 KB Output is correct
4 Correct 974 ms 166292 KB Output is correct
5 Correct 4357 ms 190128 KB Output is correct
6 Correct 3108 ms 168812 KB Output is correct
7 Correct 1454 ms 64512 KB Output is correct
8 Correct 491 ms 65420 KB Output is correct
9 Correct 1771 ms 68180 KB Output is correct
10 Correct 1450 ms 65984 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16332 KB Output is correct
2 Correct 352 ms 25252 KB Output is correct
3 Correct 436 ms 25368 KB Output is correct
4 Correct 407 ms 25264 KB Output is correct
5 Correct 500 ms 25472 KB Output is correct
6 Correct 224 ms 25220 KB Output is correct
7 Correct 440 ms 25280 KB Output is correct
8 Correct 437 ms 25272 KB Output is correct
9 Correct 509 ms 25544 KB Output is correct
10 Correct 227 ms 25248 KB Output is correct
11 Correct 426 ms 25224 KB Output is correct
12 Correct 10 ms 16204 KB Output is correct
13 Correct 2016 ms 147316 KB Output is correct
14 Correct 2760 ms 148960 KB Output is correct
15 Correct 974 ms 166292 KB Output is correct
16 Correct 4357 ms 190128 KB Output is correct
17 Correct 3108 ms 168812 KB Output is correct
18 Correct 1454 ms 64512 KB Output is correct
19 Correct 491 ms 65420 KB Output is correct
20 Correct 1771 ms 68180 KB Output is correct
21 Correct 1450 ms 65984 KB Output is correct
22 Correct 2726 ms 173696 KB Output is correct
23 Correct 2974 ms 176628 KB Output is correct
24 Correct 4207 ms 175688 KB Output is correct
25 Correct 4278 ms 179384 KB Output is correct
26 Correct 4021 ms 175228 KB Output is correct
27 Correct 5014 ms 194928 KB Output is correct
28 Correct 1089 ms 177268 KB Output is correct
29 Correct 4144 ms 174896 KB Output is correct
30 Correct 4019 ms 174452 KB Output is correct
31 Correct 4030 ms 174968 KB Output is correct
32 Correct 1566 ms 69476 KB Output is correct
33 Correct 483 ms 66120 KB Output is correct
34 Correct 1022 ms 62464 KB Output is correct
35 Correct 1068 ms 62496 KB Output is correct
36 Correct 1339 ms 62800 KB Output is correct
37 Correct 1346 ms 63144 KB Output is correct