oj.uz

Submission #920888

# Submission time Handle Problem Language Result Execution time Memory
920888 2024-02-03T07:22:08 Z Gr47 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 357672 KB 
#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 segment
{
  long long sm = 0;
  bool def = true;
};

void init(segment &res, const long long &d)
{
  res.def = false;

  // TODO: initialize for one length segment
  res.sm = d;
}

segment combine(const segment &up, const segment &down)
{
  if (up.def)
    return down;
  if (down.def)
    return up;

  segment res;
  res.def = false;

  // TODO : Comine up and down segment
  res.sm = up.sm + down.sm;

  return res;
}

struct LCA
{
  int N;
  static const int D = 20;
  vector<vector<int>> table;
  vector<vector<segment>> 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<segment>(N));
    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] = combine(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)
      init(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
  segment combined_segment(int u, int up_walk)
  {
    segment res;

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

  segment path_segment(int u, int v)
  {
    int lc = lca(u, v);
    return combine(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).sm);
  }
}

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).sm);
    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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 17240 KB Output is correct
2 Correct 1002 ms 33544 KB Output is correct
3 Correct 2229 ms 33984 KB Output is correct
4 Correct 2109 ms 33828 KB Output is correct
5 Correct 2664 ms 34040 KB Output is correct
6 Correct 308 ms 33620 KB Output is correct
7 Correct 2157 ms 33620 KB Output is correct
8 Correct 2269 ms 34096 KB Output is correct
9 Correct 2642 ms 34656 KB Output is correct
10 Correct 308 ms 33580 KB Output is correct
11 Correct 2150 ms 33724 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16984 KB Output is correct
2 Correct 7364 ms 351864 KB Output is correct
3 Execution timed out 8093 ms 357672 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 17240 KB Output is correct
2 Correct 1002 ms 33544 KB Output is correct
3 Correct 2229 ms 33984 KB Output is correct
4 Correct 2109 ms 33828 KB Output is correct
5 Correct 2664 ms 34040 KB Output is correct
6 Correct 308 ms 33620 KB Output is correct
7 Correct 2157 ms 33620 KB Output is correct
8 Correct 2269 ms 34096 KB Output is correct
9 Correct 2642 ms 34656 KB Output is correct
10 Correct 308 ms 33580 KB Output is correct
11 Correct 2150 ms 33724 KB Output is correct
12 Correct 5 ms 16984 KB Output is correct
13 Correct 7364 ms 351864 KB Output is correct
14 Execution timed out 8093 ms 357672 KB Time limit exceeded
15 Halted 0 ms 0 KB -