Submission #1258047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258047		LucaLucaM	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	358 ms	49792 KiB

meetings2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

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;
      }
    }

    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);
  std::cout.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--;
    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);  

  Tree T;
  T.build(parent);

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

  std::sort(activate.begin(), activate.end(), [&](int u, int v) {
    return sz[u] > sz[v];
  });

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

  int cur = 0;
  int diamx = centroid, diamy = centroid;

  for (int u : activate) {
    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;
      cur = dxu + 1;
    } else if (dyu > dxy) {
      diamx = u;
      cur = dyu + 1;
    }
    int maxK = std::min(n, 2 * sz[u] + 1);
    answer[maxK] = std::max(answer[maxK], cur);
  }
  
  for (int k = n - 1; k > 0; k--) {
    answer[k] = std::max(answer[k], answer[k + 1]);
  }

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

  return 0;
}

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