Submission #1273926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273926		uzukishinobu	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	297 ms	27032 KiB

meetings2

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
vector <int> z[1000005];
int res[1000005];
int del[1000005];
int child[1000005];
int sz;
void predfs(int i,int par){
    child[i]=1;
    for (auto p:z[i]){
         if (p==par || del[p]){
             continue;
         }
         predfs(p,i);
         child[i]+=child[p];
    }
}
int centroid(int i,int par){
    for (auto p:z[i]){
         if (p==par || del[p]){
             continue;
         }
         if (child[p]*2>sz){
             return centroid(p,i);
         }
    }
    return i;
}
int pre[1000005];
int t[1000005];

void dfs(int i,int par,int depth){
    child[i]=1;
    for (auto p:z[i]){
         if (p==par || del[p]){
             continue;
         }
         dfs(p,i,depth+1);
         child[i]+=child[p];
    }
    pre[child[i]]=max(pre[child[i]],depth);
}
void decompose(int i){
     predfs(i,0);
     sz=child[i];
     int cen=centroid(i,0);
     del[cen]=1;
     for (int j=1;j<=sz;j++){
          pre[j]=0;
          t[j]=0;
     }
     for (auto p:z[cen]){
          if (del[p]){
              continue;
          }
          dfs(p,cen,1);
          for (int j=child[p]-1;j>=1;j--){
               pre[j]=max(pre[j],pre[j+1]);
          }
          for (int j=1;j<=child[p];j++){
               res[j*2]=max(res[j*2],pre[j]+t[j]);
               t[j]=max(t[j],pre[j]);
          }
          for (int j=1;j<=child[p];j++){
               pre[j]=0;
          }
          
     }
     for (auto p:z[cen]){
          if (del[p]){
              continue;
          }
          decompose(p);
     }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    decompose(1);
    for (int i=1;i<=a;i++){
         if (i%2==0){
             cout << res[i]+1 << "\n";
         }else{
             cout << 1 << "\n";
         }
    }
    return 0;
}

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