Submission #944630

#	Time	Username	Problem	Language	Result	Execution time	Memory
944630		aufan	Factories (JOI14_factories)	C++17	0 / 100	134 ms	226392 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const long long INFF = 1e18;

vector<int> dep(500000), par(500000), tin(500000);
vector<long long> d(500000), ans(500000, INFF);
vector<vector<pair<int, int>>> sp(1000000, vector<pair<int, int>>(20));

void Init(int n, int a[], int b[], int d[]) {
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
      g[a[i]].push_back({b[i], d[i]});
      g[b[i]].push_back({a[i], d[i]});
  }

  int tim = 0;

  function<void(int, int)> dfs = [&](int x, int pr) {
      sp[tim][0] = {dep[x], x};
      tin[x] = tim++;

      for (auto [z, c] : g[x]) {
          if (z == pr) continue;

          dep[z] = dep[x] + 1;
          d[z] = d[x] + c;

          dfs(z, x);

          sp[tim++][0] = {dep[x], x};
      }
  };

  dfs(0, 0);

  for (int j = 1; (1 << j) <= tim; j++) {
      for (int i = 0; i + (1 << j) - 1 < tim; i++) {
          sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
      }
  }

  vector<int> sz(n), rem(n);

  function<void(int, int)> compute_subtree = [&](int x, int p) {
      sz[x] = 1;

      for (auto [z, c] : g[x]) {
          if (z == p || rem[z]) continue;

          compute_subtree(z, x);

          sz[x] += sz[z];
      }
  };

  auto get_centroid = [&](int x) {
      compute_subtree(x, -1);

      int tree_size = sz[x];
      bool found = 0;
      while (!found) {
          found = 1;
          for (auto [z, c] : g[x]) {
              if (rem[z] || sz[z] > sz[x]) continue;

              if (sz[z] > tree_size / 2) {
                  x = z;
                  found = 0;
              }
          }
      }

      return x;
  };

  function<int(int)> build_centroid_tree = [&](int x) {
      x = get_centroid(x);
      rem[x] = 1;

      for (auto [z, c] : g[x]) {
          if (rem[z]) continue;

          z = build_centroid_tree(z);

          par[z] = x;
      }

      return x;
  };

  int rt = build_centroid_tree(0);
  par[rt] = -1;
}

int lca(int x, int y) {
    x = tin[x]; y = tin[y];
    if (x > y) swap(x, y);

    int j = __lg(y - x + 1);
    return min(sp[x][j], sp[y - (1 << j) + 1][j]).second;
}

long long dist(int x, int y) {
    return d[x] + d[y] - 2 * d[lca(x, y)];
}

void update(int x) {
    int z = x;
    while (z != -1) {
        ans[z] = min(ans[z], dist(z, x));
        z = par[z];
    }
}

long long query(int x) {
    int z = x;
    long long res = INFF;
    while (z != -1) {
        res = min(res, ans[z] + dist(z, x));
        z = par[z];
    }

    return res;
}

void reset(int x) {
    int z = x;
    while (z != -1) {
        ans[z] = INFF;
        z = par[z];
    }
}

long long Query(int s, int X[], int t, int Y[]) {
  for (int i = 0; i < s; i++) {
      update(X[i]);
  }

  long long ans = INFF;
  for (int i = 0; i < t; i++) {
      ans = min(ans, query(Y[i]));
  }

  for (int i = 0; i < s; i++) {
      reset(X[i]);
  }

  return ans;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67