Submission #688519

#	Time	Username	Problem	Language	Result	Execution time	Memory
688519		peijar	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	719 ms	64624 KiB

meetings2

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 2e5;
const int MAXP = 20;

vector<int> adj[MAXN];
int sz[MAXN], depth[MAXN], par[MAXP][MAXN];

void dfsSz(int u, int p) {
  sz[u] = 1;
  for (int v : adj[u])
    if (v != p) {
      dfsSz(v, u);
      sz[u] += sz[v];
    }
}

void dfs(int u, int p) {
  par[0][u] = p;
  for (int i = 0; i < MAXP - 1; ++i)
    par[i + 1][u] = par[i][par[i][u]];
  sz[u] = 1;
  for (int v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      dfs(v, u);
      sz[u] += sz[v];
    }
}

int getLca(int u, int v) {
  if (depth[u] < depth[v])
    swap(u, v);
  int d = depth[u] - depth[v];
  for (int p = 0; p < MAXP; ++p)
    if ((1 << p) & d)
      u = par[p][u];
  if (u == v)
    return u;
  for (int p = MAXP - 1; p >= 0; --p) {
    int s = par[p][u];
    int t = par[p][v];
    if (s != t) {
      u = s;
      v = t;
    }
  }
  return par[0][u];
}

int dis(int u, int v) {
  int lca = getLca(u, v);
  return depth[u] + depth[v] - 2 * depth[lca];
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet;
  cin >> nbSommet;

  for (int i = 1; i < nbSommet; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  dfsSz(0, 0);

  int centroid = 0;
  int prv = 0;
  while (true) {
    bool found = false;
    for (int v : adj[centroid])
      if (v != prv and 2 * sz[v] >= nbSommet) {
        prv = centroid;
        centroid = v;
        found = true;
        break;
      }
    if (!found)
      break;
  }

  dfs(centroid, centroid);
  vector<vector<int>> withSz(nbSommet);
  for (int u = 0; u < nbSommet; ++u)
    if (u != centroid)
      withSz[sz[u]].push_back(u);

  vector<int> sol(nbSommet / 2 + 1);
  int s = centroid, t = centroid;
  int diameter = 0;
  for (int d = nbSommet / 2; d >= 1; --d) {
    for (int u : withSz[d]) {
      int ds = dis(s, u), dt = dis(t, u);
      if (ds > diameter)
        t = u, diameter = ds;
      else if (dt > diameter)
        s = u, diameter = dt;
    }
    sol[d] = diameter + 1;
  }
  for (int d = 1; d <= nbSommet; ++d) {
    if (d % 2)
      cout << 1 << '\n';
    else
      cout << sol[d / 2] << '\n';
  }
}

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