제출 #1286240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286240		denislav	Meetings 2 (JOI21_meetings2)	C++20	20 / 100	4091 ms	31388 KiB

meetings2

# include <iostream>
# include <vector>
using namespace std;
template<class T> void chmax(T& x, const T& y) {x=max(x,y);}

const int MAX=2e5+11,LOG=20;

int n;
vector<int> adj[MAX];
int out[MAX];

int SZ[MAX];
int H[MAX];
int st[MAX][LOG];
void dfs_lca(int curr, int par)
{
    SZ[curr]=1;
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;
        H[nxt]=H[curr]+1;
        st[nxt][0]=curr;
        dfs_lca(nxt,curr);
        SZ[curr]+=SZ[nxt];
    }
}

void lca_precalc()
{
    dfs_lca(1,0);
    for(int j=1;j<LOG;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(H[i]-(1<<j)<0) continue;
            st[i][j]=st[st[i][j-1]][j-1];
        }
    }
}

int lift(int u, int k)
{
    for(int j=LOG-1;j>=0;j--)
    {
        if(k-(1<<j)>=0)
        {
            u=st[u][j];
            k-=(1<<j);
        }
    }
    return u;
}

int get_lca(int u, int v)
{
    if(H[u]<H[v]) swap(u,v);
    for(int j=LOG-1;j>=0;j--)
    {
        if(H[u]-(1<<j)>=H[v])
        {
            u=st[u][j];
        }
    }

    if(u==v) return u;
    for(int j=LOG-1;j>=0;j--)
    {
        if(H[u]-(1<<j)>=0 and  st[u][j]!=st[v][j])
        {
            u=st[u][j];
            v=st[v][j];
        }
    }
    return st[u][0];
}

pair<int,int> sizes(int u, int v)
{
    int lca=get_lca(u,v);
    if(lca!=u and lca!=v) return {SZ[u],SZ[v]};

    bool Swap=0;
    if(u!=lca)
    {
        Swap=1;
        swap(u,v);
    }

    pair<int,int> ans;
    ans={n-SZ[lift(v,H[v]-H[u]-1)],SZ[v]};
    if(Swap) swap(ans.first,ans.second);
    return ans;
}

int sz[MAX];
int from[MAX];
int h[MAX];

void dfs(int curr, int par)
{
    sz[curr]=1;
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;

        if(from[curr]==0) from[nxt]=nxt;
        else from[nxt]=from[curr];
        h[nxt]=h[curr]+1;

        dfs(nxt,curr);
        sz[curr]+=sz[nxt];
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    lca_precalc();

    for(int i=1;i<=n;i++) out[i]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=1;
        from[i]=0;
        dfs(i,0);
        for(int u=1;u<=n;u++)
        {
            if(u==i) continue;
            //chmax(out[2*min(sz[u],n-sz[from[u]])],h[u]);
            int sz1,sz2;
            tie(sz1,sz2)=sizes(u,i);
            chmax(out[2*min(sz1,sz2)],h[u]);
        }
    }

    int start=n;
    if(start%2==1) start--;
    for(int i=start-2;i>=2;i--) out[i]=max(out[i],out[i+2]);
    for(int i=1;i<=n;i++) cout<<out[i]<<"\n";

    return 0;
}

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