제출 #1258013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258013		LucaLucaM	Meetings 2 (JOI21_meetings2)	C++20	20 / 100	4094 ms	13572 KiB

meetings2

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

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

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

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> score(n, 0);

  std::vector<int> sz(n);
  std::vector<int> dp(n);
  int answer = 0;

  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) {
      g[u].erase(std::find(g[u].begin(), g[u].end(), p));
    } 
    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);  
  
  auto dfs = [&](auto &&self, int u, int k) -> void {
    dp[u] = 0;
    for (int v : g[u]) {
      self(self, v, k);
    }
    if (sz[u] >= k / 2) {
      int max1 = 0, max2 = 0;
      for (int v : g[u]) {
        if (dp[v] >= max1) {
          max2 = max1;
          max1 = dp[v];
        } else if (dp[v] > max2) {
          max2 = dp[v];
        }
      }
      if (max2 > 0) {
        answer = std::max(answer, max1 + max2 + 1);
      }
      dp[u] = 1 + max1;
    }
    if (u != centroid) {
      answer = std::max(answer, 1 + dp[u]);
    }
  };
  
  for (int k = 1; k <= n; k++) {
    if (k % 2 == 1) {
      std::cout << 1 << ' ';
      continue;
    }
    answer = 1;
    dfs(dfs, centroid, k);
    std::cout << answer << ' ';
  }

  return 0;
}

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