Submission #1026230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026230		AdamGS	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1072 ms	30332 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7;
vector<int>V[LIM], spojna;
int usun[LIM], ile[LIM], odl[LIM], ans[2*LIM], n;
int tr[4*LIM], N;
int cnt(int l, int r) {
  l+=N; r+=N;
  int ma=max(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ma=max(ma, tr[l+1]);
    if(r%2==1) ma=max(ma, tr[r-1]);
    l/=2; r/=2;
  }
  return ma;
}
void upd(int v, int x) {
  v+=N;
  while(v) {
    tr[v]=max(tr[v], x);
    v/=2;
  }
}
void DFS(int x, int o) {
  spojna.pb(x);
  ile[x]=1;
  for(auto i : V[x]) if(!usun[i] && i!=o) {
    odl[i]=odl[x]+1;
    DFS(i, x);
    ile[x]+=ile[i];
  }
}
void DFS2(int x, int o, int p) {
  ans[2*ile[x]]=max(ans[2*ile[x]], cnt(ile[x], N-1)+odl[x]+1);
  ans[2*min(p, ile[x])]=max(ans[2*min(p, ile[x])], odl[x]+1);
  for(auto i : V[x]) if(!usun[i] && i!=o) DFS2(i, x, p);
}
void DFS3(int x, int o) {
  upd(ile[x], odl[x]);
  for(auto i : V[x]) if(!usun[i] && i!=o) DFS3(i, x);
}
int cent(int x) {
  spojna.clear();
  DFS(x, x);
  for(auto i : spojna) {
    int ma=(int)spojna.size()-ile[i];
    for(auto j : V[i]) if(!usun[j] && ile[j]<ile[i]) ma=max(ma, ile[j]);
    if(2*ma<=spojna.size()) x=i;
  }
  return x;
}
void cd(int x) {
  x=cent(x);
  spojna.clear();
  odl[x]=0;
  DFS(x, x);
  usun[x]=1;
  N=1;
  while(N<=spojna.size()) N*=2;
  rep(i, 2*N) tr[i]=-INF;
  for(auto i : V[x]) if(!usun[i]) {
    DFS2(i, x, (int)spojna.size()-ile[i]);
    DFS3(i, x);
  }
  rep(i, 2*N) tr[i]=-INF;
  reverse(all(V[x]));
  for(auto i : V[x]) if(!usun[i]) {
    DFS2(i, x, (int)spojna.size()-ile[i]);
    DFS3(i, x);
  }
  reverse(all(V[x]));
  for(auto i : V[x]) if(!usun[i]) cd(i);
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  rep(i, n-1) {
    int a, b;
    cin >> a >> b; --a; --b;
    V[a].pb(b);
    V[b].pb(a);
  }
  ans[2*LIM-1]=1;
  cd(0);
  for(int i=2*LIM-2; i; --i) ans[i]=max(ans[i+1], ans[i]);
  rep(i, n) if(i%2==0) ans[i+1]=1;
  rep(i, n) cout << ans[i+1] << '\n';
}

Compilation message (stderr)

meetings2.cpp: In function 'int cent(int)':
meetings2.cpp:55:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     if(2*ma<=spojna.size()) x=i;
      |        ~~~~^~~~~~~~~~~~~~~
meetings2.cpp: In function 'void cd(int)':
meetings2.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   while(N<=spojna.size()) N*=2;
      |         ~^~~~~~~~~~~~~~~

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