제출 #1258043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258043		LucaLucaM	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	289 ms	59164 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);  

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

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

  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]) {
      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;
          cur = dxu  + 1;
        } else if (dyu > dxy) {
          diamx = u;
          cur = dyu + 1;
        }
      }
    }

    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: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80