Submission #1012424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012424		Unforgettablepl	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	278 ms	68660 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> adj(n+1);
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    int centroid = -1;
    function<int(int,int)> find_centroid = [&](int x,int p){
        int siz = 1;
        for(int&i:adj[x])if(i!=p)siz+=find_centroid(i,x);
        if(n-siz<=n/2 and siz<=n){
            centroid = x;
            return (int)1e15;
        }
        return siz;
    };
    find_centroid(1,0);
    vector<int> depth(n+1);
    vector<vector<int>> lift(n+1,vector<int>(18));
    vector<pair<int,int>> subsizes;
    function<int(int,int,int)> dfs = [&](int x,int p,int dep){
        int siz = 1;
        lift[x][0] = p;
        depth[x] = dep;
        for(int&i:adj[x])if(i!=p)siz+=dfs(i,x,dep+1);
        subsizes.emplace_back(siz,x);
        return siz;
    };
    dfs(centroid,0,1);
    sort(subsizes.rbegin(),subsizes.rend());
    for(int bit=1;bit<18;bit++){
        for(int i=1;i<=n;i++){
            lift[i][bit] = lift[lift[i][bit-1]][bit-1];
        }
    }
    auto iter = subsizes.begin()+1;
    int diaL = centroid;
    int diaR = centroid;
    int diaLen = 1;
    auto lca = [&](int a,int b){
        if(depth[a]<depth[b])swap(a,b);
        int tar = depth[a]-depth[b];
        for(int bit=0;bit<18;bit++)if(tar&(1<<bit))a=lift[a][bit];
        if(a==b)return a;
        for(int bit=17;bit>=0;bit--)if(lift[a][bit]!=lift[b][bit]){
            a = lift[a][bit];
            b = lift[b][bit];
        }
        return lift[a][0];
    };
    auto dist = [&](int a,int b){
        return depth[a]+depth[b]-2*depth[lca(a,b)]+1;
    };
    vector<int> ans(n/2 + 1);
    for(int i=n/2;i;i--){
        while(iter!=subsizes.end() and iter->first>=i){
            // Add iter
            if(dist(iter->second,diaL)>diaLen){
                diaR = iter->second;
                diaLen++;
            } else if(dist(iter->second,diaR)>diaLen){
                diaL = iter->second;
                diaLen++;
            }
            iter++;
        }
        ans[i] = diaLen;
    }
    for(int i=1;i<=n;i++){
        if(i&1)cout<<"1\n";
        else cout<<ans[i/2]<<'\n';
    }
}

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