제출 #1146822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146822		ace5	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	225 ms	56420 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int maxlog = 20;

vector<int> g[maxn];
vector<int> per[maxn];
int binup[maxlog][maxn];
int dep[maxn];
int sz[maxn];
int mx[maxn];
int ans[maxn];
int vv[maxn];
int p[maxn];
int n;

void dfs_sz(int v,int p)
{
    sz[v] = 1;
    for(auto u:g[v])
    {
        if(u != p)
        {
            dfs_sz(u,v);
            sz[v] += sz[u];
        }
    }
    return ;
}

void dfs(int v,int pp,int d)
{
    dep[v] = d;
    p[v] = pp;
    for(int j = 0;j < maxlog;++j)
    {
        binup[j][v] = (j == 0 ? (v == 0 ? 0 : p[v]) : binup[j-1][binup[j-1][v]]);
    }
    int vu = v;
    for(int j = maxlog-1;j >= 0;--j)
    {
        if(n-sz[binup[j][vu]] >= sz[v])
        {
            vu = binup[j][vu];
        }
    }
    vu = p[vu];
    if(2*sz[v] > n)
    {
        vu = v;
    }
    mx[sz[v]] = max(mx[sz[v]],(d-dep[vu]+1));
    vv[vu] = max(vv[vu],d);
    for(auto u:g[v])
    {
        if(u != pp)
            dfs(u,v,d+1);
    }
    return ;
}

int dfs2(int v,int p)
{
    int tvv = vv[v];
    for(auto u:g[v])
    {
        if(u != p)
        {
            tvv = max(tvv,dfs2(u,v));
        }
    }
   // cout << n-sz[v]+1 << ' ' << v << ' ' << tvv-dep[v]+1 << endl;
    mx[n-sz[v]] = max(mx[n-sz[v]],tvv-dep[v]+2);
    return tvv;
}

int dfs_ans(int v,int p)
{
    vector<int> ind;
    for(auto u:g[v])
    {
        if(u != p)
        {
            ind.push_back(dfs_ans(u,v));
            if(per[ind.back()].size() > per[ind[0]].size())
                swap(ind.back(),ind[0]);
        }
    }
    if(ind.size() == 0)
    {
        vector<int> xx = {dep[v]};
        per[v] = xx;
        return v;
    }
    else
    {
        for(int i = 1;i < ind.size();++i)
        {
            for(int j = 0;j < per[ind[i]].size();++j)
            {
                ans[j+1] = max(ans[j+1],per[ind[i]][j] + per[ind[0]][j] - 2*dep[v] + 1);
                per[ind[0]][j] = max(per[ind[0]][j],per[ind[i]][j]);
            }
        }
        int y = per[ind[0]].size();
        for(int u = 0;u < sz[v]-y;++u)
        {
            per[ind[0]].push_back(dep[v]);
        }
        return ind[0];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int j = 0;j < n-1;++j)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs_sz(0,-1);
    dfs(0,-1,0);
    dfs2(0,-1);
    dfs_ans(0,-1);
    int tmx = 0;
    for(int j = n;j >= 0;--j)
    {
        tmx = max(tmx,mx[j+1]);
        ans[j+1] = max(ans[j+1],tmx);
    }
    for(int j = 0;j < n;++j)
    {
        cout << (j%2 == 0 ? 1 : ans[j/2+1]) << "\n";
    }
}

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