Submission #920902

#	Time	Username	Problem	Language	Result	Execution time	Memory
920902		Gr47	Factories (JOI14_factories)	C++17	15 / 100	8099 ms	261360 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

class CentroidDecomposition
{
private:
  int n;
  vector<bool> vis;
  vector<int> sz;
  const vector<vector<int>> &tree;

  int find_size(int v, int p = -1)
  {
    if (vis[v])
      return 0;
    sz[v] = 1;
    for (const int &x : tree[v])
      if (x != p)
        sz[v] += find_size(x, v);
    return sz[v];
  }

  int find_centroid(int v, int p, int cur_sz)
  {
    for (const int &x : tree[v])
      if (x != p)
        if (!vis[x] && sz[x] > (cur_sz / 2))
          return find_centroid(x, v, cur_sz);
    return v;
  }

  void init_centroid(int v, int p)
  {
    find_size(v);
    int c = find_centroid(v, -1, sz[v]);
    vis[c] = true;
    centroid_par[c] = p;
    if (p == -1)
      root = c;
    else
      centorid_tree[p].push_back(c);
    for (const int &x : tree[c])
      if (!vis[x])
        init_centroid(x, c);
  }

public:
  vector<vector<int>> centorid_tree;
  vector<int> centroid_par;
  int root;
  CentroidDecomposition(vector<vector<int>> &_tree) : tree(_tree)
  {
    root = 0;
    n = tree.size();
    centorid_tree.resize(n);
    vis.resize(n, false);
    sz.resize(n, 0);
    centroid_par.resize(n, -1);
    init_centroid(0, -1);
  }
};

struct LCA
{
  int N;
  static const int D = 20;
  vector<vector<int>> table;
  vector<vector<long long>> seg;
  vector<int> depth;

  LCA(vector<vector<int>> &tree, map<pair<int, int>, long long> &edge)
  {
    N = tree.size();
    depth.assign(N, 0);
    table.assign(D, vector<int>(N, -1));
    seg.assign(D, vector<long long>(N, 0LL));
    dfs(0, -1, tree, edge);
    for (int i = 1; i < D; i++)
    {
      for (int u = 0; u < N; u++)
      {
        if (table[i - 1][u] >= 0)
        {
          table[i][u] = table[i - 1][table[i - 1][u]];
          seg[i][u] = seg[i - 1][table[i - 1][u]] + seg[i - 1][u];
        }
        else
          table[i][u] = -1;
      }
    }
  }

  void dfs(int u, int p, vector<vector<int>> &tree, map<pair<int, int>, long long> &edge)
  {
    table[0][u] = p;

    if (p != -1)
      seg[0][u] = edge[make_pair(u, p)];

    for (int v : tree[u])
    {
      if (v == p)
        continue;
      depth[v] = depth[u] + 1;
      dfs(v, u, tree, edge);
    }
  }

  int up(int u, int dist)
  {
    for (int i = D - 1; i >= 0; i--)
    {
      if ((dist & (1 << i)) > 0)
      {
        u = table[i][u];
        if (u == -1)
          return -1;
      }
    }
    return u;
  }

  int lca(int u, int v)
  {
    if (depth[u] < depth[v])
    {
      return lca(v, u);
    }

    int diff = depth[u] - depth[v];
    u = up(u, diff);
    if (u == v)
      return u;

    for (int i = D - 1; i >= 0; i--)
    {
      if (table[i][u] != table[i][v])
      {
        u = table[i][u];
        v = table[i][v];
      }
    }
    return table[0][u];
  }

  int distance(int u, int v)
  {
    int w = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[w];
  }

  // get combined segment for [u(0),u(1),u(2),....u(up_walk)] where u(i+1) is parent of u(i) and u(0) = u
  long long combined_segment(int u, int up_walk)
  {
    long long res = 0;

    for (int i = D - 1; i >= 0; i--)
    {
      if ((up_walk & (1 << i)) > 0)
      {
        res += seg[i][u];
        u = table[i][u];
      }
    }
    return res;
  }

  long long path_segment(int u, int v)
  {
    int lc = lca(u, v);
    return combined_segment(u, depth[u] - depth[lc]) + combined_segment(v, depth[v] - depth[lc]);
  }
};

LCA *lca;
CentroidDecomposition *cd;
vector<long long> best;
const long long inf = 1e18;
void Init(int N, int A[], int B[], int D[])
{
  map<pair<int, int>, long long> edge;
  vector<vector<int>> tree(N);
  for (int i = 0; i < N - 1; i++)
  {
    tree[A[i]].push_back(B[i]);
    tree[B[i]].push_back(A[i]);
    edge[make_pair(A[i], B[i])] = D[i];
    edge[make_pair(B[i], A[i])] = D[i];
  }
  lca = new LCA(tree, edge);
  cd = new CentroidDecomposition(tree);
  best.resize(N, inf);
}

void add_node(int u)
{
  best[u] = 0;
  int p = u;
  while (p != cd->root)
  {
    p = cd->centroid_par[p];
    best[p] = min(best[p], lca->path_segment(u, p));
  }
}

void rem_node(int u)
{
  best[u] = inf;
  int p = u;
  while (p != cd->root)
  {
    p = cd->centroid_par[p];
    if (best[p] == inf)
      break;
    best[p] = inf;
  }
}

long long get_min_dist(int u)
{
  long long ans = inf;
  int cur = u;
  while (cur != -1)
  {
    ans = min(ans, best[cur] + lca->path_segment(u, cur));
    cur = cd->centroid_par[cur];
  }
  return ans;
}

long long Query(int S, int X[], int T, int Y[])
{
  long long ans = inf;
  for (int i = 0; i < S; i++)
    add_node(X[i]);
  for (int i = 0; i < T; i++)
    ans = min(ans, get_min_dist(Y[i]));
  for (int i = 0; i < S; i++)
    rem_node(X[i]);
  return ans;
}

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