Submission #1197458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197458		mychecksedad	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	638 ms	61932 KiB

meetings2

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2e5+100, M = 1e5+10, K = 52, MX = 30;


int n, s[N], num, dep[N], ans[N], A[N*2];
vi g[N];
bitset<N> vis;
vector<pii> T[N];

void build(int sz){
  for(int i = 1; i <= 2*sz + 1; ++i) A[i] = 0;
}

void upd(int v, int val){
  v += num;
  A[v] = max(A[v], val);
  for(v >>= 1; v > 0; v >>= 1) A[v] = max(A[v<<1], A[v<<1|1]);
}

int get(int l, int r){
  int res = 0;
  l += num;
  r += num + 1;
  for(; l < r; l >>= 1, r >>= 1){
    if(l & 1) res = max(res, A[l++]);
    if(r & 1) res = max(res, A[--r]);
  }
  return res;
}


void pre(int v, int p){
  s[v] = 1;
  for(int u: g[v]){
    if(u == p || vis[u]) continue;
    pre(u, v);
    s[v] += s[u];
  }
}

int centro(int v, int p){
  for(int u: g[v]){
    if(u == p || vis[u]) continue;
    if(s[u] >= (num+1)/2) return centro(u, v);
  }
  return v;
}

void dfs(int v, int p, int t){
  s[v] = 1;
  dep[v] = dep[p] + 1;
  for(int u: g[v]){
    if(vis[u] || u == p) continue;
    dfs(u, v, t);
    s[v] += s[u];
  }
  T[t].pb({s[v], dep[v]});
}

void f(int v){
  pre(v, v);
  num = s[v];
  v = centro(v, v);
  dep[v] = 0;
  for(int u: g[v]){
    if(!vis[u]){
      T[u].clear();
      dfs(u, v, u);
    }
  }
  build(num);
  for(int u: g[v]){
    if(!vis[u]){
      for(auto [sub, d]: T[u]){
        ans[sub] = max(ans[sub], d + get(sub, num) + 1);
      }

      for(auto [sub, d]: T[u]){
        upd(sub, d);
      }
    }
  }

  // cout << v << ' ' << num << " hell\n";

  build(num);
  reverse(all(g[v]));
  for(int u: g[v]){
    if(!vis[u]){
      for(auto [sub, d]: T[u]){
        ans[sub] = max(ans[sub], d + get(sub, num) + 1);
        // cout << v << ' ' << u << ' ' << sub << ' ' << d << ' ' << get(sub, num) << '\n';
      }

      for(auto [sub, d]: T[u]){
        upd(sub, d);
      }
    }
  }


  vis[v] = 1;
  for(int u: g[v]){
    if(!vis[u]) f(u);
  }
}

void solve(){
  cin >> n;
  for(int i = 1; i < n; ++i){
    int u, v; cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  for(int i = 1; i <= n; ++i){
    ans[i] = 1;
  }
  f(1);  
  for(int i = n-1; i >= 1; --i) ans[i] = max(ans[i], ans[i + 1]);

  for(int i = 1; i <= n; ++i){
    if(i&1) cout << 1 << '\n';
    else cout << ans[i/2] << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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