제출 #1286228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286228		denislav	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	2 ms	576 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,INF=1e9;

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

int spec,add_spec;
bool banned[MAX];
int sz[MAX];
int h[MAX];
int from[MAX];
void dfs_sz(int curr, int par)
{
    sz[curr]=1;
    for(int nxt: adj[curr])
    {
        if(nxt==par or banned[nxt]) continue;

        if(from[curr]==0) from[nxt]=nxt;
        else from[nxt]=from[curr];
        h[nxt]=h[curr]+1;
        dfs_sz(nxt,curr);
        sz[curr]+=sz[nxt];
    }
    if(curr==spec) sz[curr]+=add_spec;
}

int get_centroid(int curr, int par, int N)
{
    for(int nxt: adj[curr])
    {
        if(nxt==par or banned[nxt]) continue;
        if(sz[nxt]*2>N) return get_centroid(nxt,curr,N);
    }
    return curr;
}

struct segtree
{
    int tree[MAX*4];

    void build(int v=1, int l=0, int r=n)
    {
        if(l==r)
        {
            tree[v]=-INF;
            return ;
        }

        int mid=(l+r)/2;
        build(v*2,l,mid);
        build(v*2+1,mid+1,r);
        tree[v]=max(tree[v*2],tree[v*2+1]);
    }

    void update(int pos, int d, int v=1, int l=0, int r=n)
    {
        if(l==r)
        {
            if(d==-INF) tree[v]=d;
            else tree[v]=max(tree[v],d);
            return ;
        }

        int mid=(l+r)/2;
        if(pos<=mid) update(pos,d,v*2,l,mid);
        else update(pos,d,v*2+1,mid+1,r);
        tree[v]=max(tree[v*2],tree[v*2+1]);
    }

    int query(int le, int ri, int v=1, int l=0, int r=n)
    {
        if(ri<l or r<le) return -INF;
        if(le<=l and r<=ri) return tree[v];

        int mid=(l+r)/2;
        return max(query(le,ri,v*2,l,mid),query(le,ri,v*2+1,mid+1,r));
    }
}tree;

int N;

void dfs1(int curr, int par)
{
    int sz1=sz[curr],sz2=N-sz[from[curr]];
    chmax(out[min(sz1,sz2)*2],h[curr]);
    chmax(out[sz1*2],h[curr]+tree.query(sz1,n));

    for(int nxt: adj[curr])
    {
        if(nxt==par or banned[nxt]) continue;
        dfs1(nxt,curr);
    }
}

vector<int> rollback;
void dfs2(int curr, int par)
{
    int sz1=sz[curr];
    tree.update(sz1,h[curr]);
    rollback.push_back(sz1);

    for(int nxt: adj[curr])
    {
        if(nxt==par or banned[nxt]) continue;
        dfs2(nxt,curr);
    }
}

void cd(int curr, int special)
{
    spec=-1;
    dfs_sz(curr,0);
    N=sz[curr];
    curr=get_centroid(curr,0,sz[curr]);

    spec=special;
    add_spec=n-N;
    from[curr]=0;
    h[curr]=0;
    dfs_sz(curr,0);

    //cout<<"->"<<curr<<"\n";
    //for(int i=1;i<=n;i++) cout<<i<<":"<<h[i]<<" "<<from[i]<<"\n";

    for(int nxt: adj[curr])
    {
        if(banned[nxt]) continue;
        dfs1(nxt,curr);
        dfs2(nxt,curr);
    }

    for(int x: rollback) tree.update(x,-INF);
    rollback.clear();

    banned[curr]=1;
    for(int nxt: adj[curr])
    {
        if(banned[nxt]) continue;
        cd(nxt,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);
    }

    tree.build();
    cd(1,-1);

    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++) out[i]++;
    for(int i=1;i<=n;i++) cout<<out[i]<<"\n";

    return 0;
}

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