Submission #1258033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258033		LucaLucaM	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	0 ms	328 KiB

meetings2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include <chrono>
#include <set>
using ll = long long;
#define debug(x) #x << " = " << x << '\n'

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

struct Tree {
  int n;
  int logn;

  std::vector<int> p;
  std::vector<std::vector<int>> jump;
  std::vector<int> depth;
  std::vector<std::vector<int>> g;

  void build(const std::vector<int> & _p) {
    p = _p;
    n = (int) p.size();
    logn = std::__lg(n);
    
    depth.resize(n);
    jump = std::vector<std::vector<int>>(logn + 1, std::vector<int>(n));
    g.resize(n);
    for (int i = 0; i < n; i++) {
      jump[0][i] = p[i];
    }
    
    for (int j = 1; j <= logn; j++) {
      for (int i = 0; i < n; i++) {
        jump[j][i] = jump[j - 1][jump[j - 1][i]];
      }
    }

    int root = -1;
    for (int i = 0; i < n; i++) {
      if (p[i] != i) {
        g[p[i]].push_back(i);
      } else {
        root = i;
      }
    }

    assert(root != -1);

    auto dfs = [&](auto &&self, int u) -> void {
      for (int v : g[u]) {
        depth[v] = 1 + depth[u];
        self(self, v);
      }
    };

    depth[root] = 0;
    dfs(dfs, root);
  }
  
  int up(int u, int d) {
    for (int k = logn; k >= 0; k--) {
      if (d >> k & 1) {
        u = jump[k][u];
      }
    }
    return u;
  }
  int lca(int u, int v) {
    if (depth[u] < depth[v]) {
      std::swap(u, v);
    }
    u = up(u, depth[u] - depth[v]);
    if (u == v) {
      return u;
    }
    for (int k = logn; k >= 0; k--) {
      if (jump[k][u] != jump[k][v]) {
        u = jump[k][u];
        v = jump[k][v];
      }
    }
    return jump[0][u];
  }
  
  int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  std::vector<std::vector<int>> g(n);

  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    u--, v--;
    // u = i;
    // v = rng() % i;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  std::vector<int> sz(n);
  std::vector<int> parent(n);

  auto dfs0 = [&](auto &&self, int u, int p) -> void {
    sz[u] = 1;
    for (int v : g[u]) {
      if (v != p) {
        self(self, v, u);
        sz[u] += sz[v];
      }
    }
  };

  auto find_centroid = [&](auto &&self, int u, int p) -> int {
    for (int v : g[u]) {
      if (v != p && 2 * sz[v] > n) {
        return self(self, v, u);
      }
    }
    return u;
  };

  auto dfs1 = [&](auto &&self, int u, int p) -> void {
    if (p != -1) {
      parent[u] = p;
      g[u].erase(std::find(g[u].begin(), g[u].end(), p));
    } else {
      parent[u] = u;
    }
    sz[u] = 1;
    for (int v : g[u]) {
      self(self, v, u);
      sz[u] += sz[v];
    }
  };

  dfs0(dfs0, 0, -1);
  int centroid = find_centroid(find_centroid, 0, -1);
  dfs1(dfs1, centroid, -1);  

  std::vector<std::vector<int>> activate(n + 1);
  
  for (int i = 0; i < n; i++) {
    // sz[i] >= k / 2 <=> 2 * sz[i] + 1 >= k <=> k <= 2 * sz[i] + 1
    if (i != centroid) {
      activate[std::min(n, 2 * sz[i] + 1)].push_back(i);
    }
  }

  std::vector<int> answer(n + 1, 1);
  std::vector<int> dp(n, 0); 

  int cur = 0;
  
  Tree T;
  T.build(parent);

  std::vector<std::pair<int, int>> diam(n);
  for (int i = 0; i < n; i++) {
    diam[i] = {i, i};
  }

  std::vector<int> maxDepth(n, 0);
  
  std::multiset<int> st;
  for (int v : g[centroid]) {
    st.insert(0);
  }

  auto best2 = [&]() {
    int ret = 0;
    auto it = st.rbegin();
    ret += *it;
    ++it;
    if ((*it) == 0) {
      return ret - 1;
    }
    ret += *it;
    return ret;
  };

  int diamx = -1, diamy = -1;
  cur = 2;

  for (int k = n; k > 0; k--) {
    std::sort(activate[k].begin(), activate[k].end(), [&](int u, int v) {
      return T.depth[u] > T.depth[v];
    });
    for (int u : activate[k]) {
      int uu = T.up(u, T.depth[u] - 1);
      if (diamx == -1) {
        diamx = diamy = u;
      } else {
        int dxy = T.dist(diamx, diamy);
        int dxu = T.dist(diamx, u);
        int dyu = T.dist(diamy, u);
        if (dxu > dxy && dxu >= dyu) {
          diamy = u;
        } else if (dyu > dxy) {
          diamx = u;
        }
      }
      // std::cout << debug(u);
      // if (u == 3) {
      //   std::cout << T.dist(2, 4) << '\n';
      //   std::cout << T.dist(2, 3) << '\n';
      //   std::cout << " ? " << diamx << ' ' << diamy << '\n';
      // }
      cur = std::max(cur, T.dist(diamx, diamy) + 1);
      cur = std::max(cur, T.depth[u]);
    }
    // std::cout << debug(k);

    if (k % 2 == 1) {
      answer[k] = 1;
    } else {
      answer[k] = cur;
    }
  }

  for (int k = 1; k <= n; k++) {
    std::cout << answer[k] << ' ';
  }

  return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80