Submission #955219

#	Time	Username	Problem	Language	Result	Execution time	Memory
955219		abczz	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	1467 ms	79596 KiB

meetings2

#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <map>
#define ll long long
 
using namespace std;
 
vector <ll> adj[200000];
bool C[200000];
vector <array<ll, 2>> U;
vector <ll> V[200000];
vector <vector<ll>> D;
bool ok;
ll n, k, a, b, f = 1e18, g, sz[200000], F[200000];
 
struct SegTree{
  vector <ll> st{vector <ll> (800000, -1e18)};
  vector <ll> updated;
  void update(ll id, ll l, ll r, ll q, ll w) {
    updated.push_back(id);
    if (l == r) {
      st[id] = max(st[id], w);
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, w);
    else update(id*2+1, mid+1, r, q, w);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll q) {
    if (r < q) return -1e18;
    if (q <= l) return st[id];
    ll mid = (l+r)/2;
    return max(query(id*2, l, mid, q), query(id*2+1, mid+1, r, q));
  }
  void rollback() {
    while (!updated.empty()) {
      auto id = updated.back();
      updated.pop_back();
      st[id] = -1e18;
    }
  }
}ST;
 
void dfs_sz(ll u, ll p) {
  sz[u] = 1;
  for (auto v : adj[u]) {
    if (v != p && !C[v]) {
      dfs_sz(v, u);
      sz[u] += sz[v];
    }
  }
  if (ok) g = max(g, min(sz[u], n-sz[u]));
}
 
ll find_cent(ll u, ll p, ll tot) {
  ll mx = -1, ret = -1;
  for (auto v : adj[u]) {
    if (v != p && !C[v]) {
      ret = max(ret, find_cent(v, u, tot));
      mx = max(mx, sz[v]);
    }
  }
  mx = max(mx, tot-sz[u]);
  if (mx <= tot/2) return u;
  else return ret;
}
 
void dfs_resz(ll u, ll p, ll w, ll x) {
  if (D[x].size() == w) D[x].push_back(0);
  sz[u] = 1;
  for (auto v : adj[u]) {
    if (v != p && !C[v]) {
      dfs_resz(v, u, w+1, x);
      sz[u] += sz[v];
    }
  }
  D[x][w] = max(D[x][w], sz[u]);
}
 
void solve(ll u) {
  dfs_sz(u, -1);
  ok = 0;
  ll tot = sz[u];
  ll cent = find_cent(u, -1, tot);
  C[cent] = 1;
  map <ll, ll> mp;
  D.clear();
  ll x = 0;
  for (auto v : adj[cent]) {
    if (!C[v]) {
      D.push_back({});
      dfs_resz(v, cent, 0, x);
      for (int i=0; i<D[x].size(); ++i) {
        F[D[x][i]-1] = max(F[D[x][i]-1], ST.query(1, 0, n-1, D[x][i]-1) + i + 3);
        F[min(D[x][i], tot-sz[v])-1] = max(F[min(D[x][i], tot-sz[v])-1], (ll)i + 2);
      }
      for (int i=0; i<D[x].size(); ++i) {
        ST.update(1, 0, n-1, D[x][i]-1, i);
      }
      ++x;
    }
  }
  ST.rollback();
  while (x--) {
    for (int i=0; i<D[x].size(); ++i) {
      F[D[x][i]-1] = max(F[D[x][i]-1], ST.query(1, 0, n-1, D[x][i]-1) + i + 3);
      //cout << cent+1 << " " << ST.query(1, 0, n-1, D[x][i]-1) << " " << i << '\n';
    }
    for (int i=0; i<D[x].size(); ++i) {
      ST.update(1, 0, n-1, D[x][i]-1, i);
    }
  }
  ST.rollback();
  for (auto v : adj[cent]) {
    if (!C[v]) solve(v);
  }
}
 
int main() {
  cin >> n;
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  ok = 1;
  solve(0);
  for (int i=n-2; i>=0; --i) {
    F[i] = max(F[i], F[i+1]);
    if (i <= g-1) F[i] = max(2LL, F[i]);
  }
  for (int i=0; i<n; ++i) {
    if (!(i & 1)) cout << "1\n";
    else cout << max(1LL, F[i/2]) << '\n';
  }
}

Compilation message (stderr)

meetings2.cpp: In function 'void dfs_resz(long long int, long long int, long long int, long long int)':
meetings2.cpp:72:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   72 |   if (D[x].size() == w) D[x].push_back(0);
      |       ~~~~~~~~~~~~^~~~
meetings2.cpp: In function 'void solve(long long int)':
meetings2.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |       for (int i=0; i<D[x].size(); ++i) {
      |                     ~^~~~~~~~~~~~
meetings2.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |       for (int i=0; i<D[x].size(); ++i) {
      |                     ~^~~~~~~~~~~~
meetings2.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for (int i=0; i<D[x].size(); ++i) {
      |                   ~^~~~~~~~~~~~
meetings2.cpp:112:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (int i=0; i<D[x].size(); ++i) {
      |                   ~^~~~~~~~~~~~

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