Submission #1187149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187149		KhoaDuy	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	3 ms	4932 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAXN=2*1e5;
int ans[MAXN+1],sz[MAXN+1],suf[MAXN+1],bst[MAXN+1];
bool del[MAXN+1];
vector<vector<int>> graph(MAXN+1);
void setup(int u,int p){
    sz[u]=1;
    for(int v:graph[u]){
        if(v!=p&&!del[v]){
            setup(v,u);
            sz[u]+=sz[v];
        }
    }
}
int getcen(int u,int p,int n){
    for(int v:graph[u]){
        if(v!=p&&!del[v]&&2*sz[v]>n){
            return getcen(v,u,n);
        }
    }
    return u;
}
void DFS(int u,int p,int depth){
    ans[2*sz[u]]=max(ans[2*sz[u]],depth+1);
    bst[sz[u]]=max(bst[sz[u]],depth);
    for(int v:graph[u]){
        if(v!=p&&!del[v]){
            DFS(v,u,depth+1);
        }
    }
}
void decom(int u){
    setup(u,-1);
    u=getcen(u,-1,sz[u]);
    setup(u,-1);
    for(int v:graph[u]){
        if(!del[v]){
            DFS(v,u,1);
            for(int i=1;i<=sz[v];i++){
                ans[2*i]=max(ans[2*i],bst[i]+suf[i]+1);
            }
            int curr=-1e9;
            for(int i=sz[v];i>=1;i--){
                curr=max(curr,bst[i]);
                bst[i]=-1e9;
                suf[i]=max(suf[i],curr);
            }
        }
    }
    for(int i=1;i<=sz[u];i++){
        suf[i]=-1e9;
    }
    for(int br=graph[u].size()-1;br>=0;br--){
        int v=graph[u][br];
        if(!del[v]){
            DFS(v,u,1);
            for(int i=1;i<=sz[v];i++){
                ans[2*i]=max(ans[2*i],bst[i]+suf[i]+1);
            }
            int curr=-1e9;
            for(int i=sz[v];i>=1;i--){
                curr=max(curr,bst[i]);
                bst[i]=-1e9;
                suf[i]=max(suf[i],curr);
            }
        }
    }
    for(int i=1;i<=sz[u];i++){
        suf[i]=-1e9;
    }
    del[u]=true;
    for(int v:graph[u]){
        if(!del[v]){
            decom(v);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        ans[i]=1,bst[i]=-1e9,suf[i]=-1e9;
    }
    for(int i=0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    decom(1);
    for(int i=n-1;i>=1;i--){
        ans[i]=max(ans[i],ans[i+1]);
    }
    for(int i=1;i<=n;i++){
        cout << ans[i] << endl;
    }
}

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