oj.uz

Submission #235569

# Submission time Handle Problem Language Result Execution time Memory
235569 2020-05-28T15:30:32 Z ADMathNoob Factories (JOI14_factories) C++11
100 / 100
 5975 ms 178532 KB 
#include <bits/stdc++.h>

#ifndef _DEBUG
#include "factories.h"
#endif

using namespace std;


const long long INF = 1e18;
const int N = 500005;
const int H = 21;

int n;
vector<pair<int, int>> g[N];

int pv[N];
vector<int> order;
long long dist[N];
int sz[N];

int cpv[N];
int cdepth[N];
long long f[H][N];

long long best[N];

void dfs(int v, int p) {
  pv[v] = p;
  sz[v] = 1;
  order.push_back(v);
  for (const auto& e : g[v]) {
    int u = e.first;
    int w = e.second;
    if (u == p || cdepth[u] != -1) {
      continue;
    }
    dist[u] = dist[v] + w;
    dfs(u, v);
    sz[v] += sz[u];
  }
}

void do_dfs_from(int v) {
  order.clear();
  dist[v] = 0;
  dfs(v, -1);
}

int centroid(int v) {
  do_dfs_from(v);
  for (int i : order) {
    bool ok = (sz[v] - sz[i] <= sz[v] / 2);
    for (const auto& e : g[i]) {
      int u = e.first;
      if (u == pv[i] || cdepth[u] != -1) {
        continue;
      }
      ok &= (sz[u] <= sz[v] / 2);
    }
    if (ok) {
      return i;
    }
  }
  assert(0);
}

void cdfs(int v, int p) {
  cpv[v] = p;
  do_dfs_from(v);
  for (int i : order) {
    f[cdepth[v]][i] = dist[i];
  }
  // cerr << "centroid: " << v << '\n';
  for (const auto& e : g[v]) {
    int u = e.first;
    if (cdepth[u] != -1) {
      continue;
    }
    u = centroid(u);
    cdepth[u] = cdepth[v] + 1;
    cdfs(u, v);
  }
}

void build_centroid() {
  fill(cdepth, cdepth + N, -1);
  int c = centroid(0);
  cdepth[c] = 0;
  cdfs(c, -1);
}

void Init(int _n, int a[], int b[], int d[]) {
  n = _n;
  for (int i = 0; i < n - 1; i++) {
    g[a[i]].emplace_back(b[i], d[i]);
    g[b[i]].emplace_back(a[i], d[i]);
  }
  build_centroid();
  fill(best, best + N, INF);
}

void update(int v) {
  for (int u = v; u != -1; u = cpv[u]) {
    best[u] = min(best[u], f[cdepth[u]][v]);
  }
}

long long get(int v) {
  long long res = INF;
  for (int u = v; u != -1; u = cpv[u]) {
    res = min(res, f[cdepth[u]][v] + best[u]);
  }
  return res;
}

void reset(int v) {
  while (v != -1) {
    best[v] = INF;
    v = cpv[v];
  }
}

long long Query(int s, int x[], int t, int y[]) {
  for (int i = 0; i < s; i++) {
    update(x[i]);
  }
  long long ans = INF;
  for (int i = 0; i < t; i++) {
    ans = min(ans, get(y[i]));
  }
  for (int i = 0; i < s; i++) {
    reset(x[i]);
  }
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18688 KB Output is correct
2 Correct 401 ms 27280 KB Output is correct
3 Correct 452 ms 36472 KB Output is correct
4 Correct 438 ms 36448 KB Output is correct
5 Correct 470 ms 36600 KB Output is correct
6 Correct 329 ms 35832 KB Output is correct
7 Correct 437 ms 36356 KB Output is correct
8 Correct 438 ms 36600 KB Output is correct
9 Correct 464 ms 36748 KB Output is correct
10 Correct 333 ms 35960 KB Output is correct
11 Correct 437 ms 36472 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18176 KB Output is correct
2 Correct 2617 ms 120480 KB Output is correct
3 Correct 4196 ms 146664 KB Output is correct
4 Correct 845 ms 90204 KB Output is correct
5 Correct 5043 ms 178532 KB Output is correct
6 Correct 4111 ms 157280 KB Output is correct
7 Correct 1228 ms 62324 KB Output is correct
8 Correct 502 ms 51820 KB Output is correct
9 Correct 1404 ms 66152 KB Output is correct
10 Correct 1260 ms 63860 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18688 KB Output is correct
2 Correct 401 ms 27280 KB Output is correct
3 Correct 452 ms 36472 KB Output is correct
4 Correct 438 ms 36448 KB Output is correct
5 Correct 470 ms 36600 KB Output is correct
6 Correct 329 ms 35832 KB Output is correct
7 Correct 437 ms 36356 KB Output is correct
8 Correct 438 ms 36600 KB Output is correct
9 Correct 464 ms 36748 KB Output is correct
10 Correct 333 ms 35960 KB Output is correct
11 Correct 437 ms 36472 KB Output is correct
12 Correct 16 ms 18176 KB Output is correct
13 Correct 2617 ms 120480 KB Output is correct
14 Correct 4196 ms 146664 KB Output is correct
15 Correct 845 ms 90204 KB Output is correct
16 Correct 5043 ms 178532 KB Output is correct
17 Correct 4111 ms 157280 KB Output is correct
18 Correct 1228 ms 62324 KB Output is correct
19 Correct 502 ms 51820 KB Output is correct
20 Correct 1404 ms 66152 KB Output is correct
21 Correct 1260 ms 63860 KB Output is correct
22 Correct 3168 ms 126060 KB Output is correct
23 Correct 3210 ms 130440 KB Output is correct
24 Correct 4973 ms 144352 KB Output is correct
25 Correct 4933 ms 147876 KB Output is correct
26 Correct 5020 ms 144704 KB Output is correct
27 Correct 5975 ms 163220 KB Output is correct
28 Correct 1039 ms 80860 KB Output is correct
29 Correct 4903 ms 144432 KB Output is correct
30 Correct 5493 ms 143992 KB Output is correct
31 Correct 4895 ms 144380 KB Output is correct
32 Correct 1375 ms 66968 KB Output is correct
33 Correct 507 ms 52236 KB Output is correct
34 Correct 969 ms 57748 KB Output is correct
35 Correct 974 ms 57708 KB Output is correct
36 Correct 1277 ms 60744 KB Output is correct
37 Correct 1347 ms 60776 KB Output is correct