Submission #1034847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034847		alexdd	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	714 ms	80156 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int n;
int parent[200005],siz[200005],depth[200005];
vector<int> con[200005];
int anc[200005][18];
int cine[400005];
int tin[200005],tout[200005],timer;
vector<int> unde[200005];
void dfs(int nod)
{
    tin[nod]=++timer;
    cine[timer]=nod;
    unde[nod].push_back(timer);

    siz[nod]=1;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            parent[adj]=nod;
            anc[adj][0]=nod;
            depth[adj]=depth[nod]+1;
            dfs(adj);
            cine[++timer]=nod;
            unde[nod].push_back(timer);
            siz[nod]+=siz[adj];
        }
    }
    tout[nod]=timer;
}

struct node
{
    int a,b,ab,bc,abc;
};
node combine(node x, node y)
{
    node aux;
    aux.a = max(x.a, y.a);
    aux.b = max(x.b, y.b);
    aux.ab = max({x.ab, y.ab, x.a+y.b});
    aux.bc = max({x.bc, y.bc, x.b+y.a});
    aux.abc = max({x.abc, y.abc, x.a+y.bc, x.ab+y.a});
    return aux;
}
node aint[1100000];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod] = {-INF,-INF,-INF,-INF,-INF};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
void upd(int nod, int st, int dr, int poz, int newv)
{
    if(st==dr)
    {
        aint[nod].a = newv;
        aint[nod].b = -2*newv;
        aint[nod].ab = aint[nod].bc = aint[nod].abc = -INF;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return {-INF,-INF,-INF,-INF,-INF};
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}


int rez[200005];
signed main()
{
    cin>>n;
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    dfs(1);
    build(1,1,timer);
    anc[1][0]=1;
    for(int p=1;p<18;p++)
        for(int i=1;i<=n;i++)
            anc[i][p] = anc[anc[i][p-1]][p-1];
    vector<pair<pair<int,int>,int>> v;
    for(int i=1;i<=n;i++)
    {
        v.push_back({{-siz[i],0},i});
        v.push_back({{-(n-siz[i]),1},i});
    }
    sort(v.begin(),v.end());
    for(auto x:v)
    {
        int i=x.second;
        int tip=x.first.second;
        //cout<<i<<" "<<tip<<" zzz\n";
        if(tip==0)
        {
            for(auto x:unde[i])
                upd(1,1,timer,x,depth[i]);

            int cap=i;
            for(int p=17;p>=0;p--)
                if(n-siz[anc[cap][p]]>=siz[i])
                    cap = anc[cap][p];
            if(cap!=1 && n-siz[cap]>=siz[i])
                cap = parent[cap];
            rez[siz[i]] = max(rez[siz[i]], qry(1,1,timer,tin[cap],tout[cap]).abc+1);
        }
        else
        {
            rez[n-siz[i]] = max(rez[n-siz[i]], qry(1,1,timer,tin[i],tout[i]).a-depth[i]+2);
        }
    }
    for(int i=n-1;i>0;i--)
        rez[i] = max({1, rez[i], rez[i+1]});
    for(int i=1;i<=n;i++)
    {
        if(i%2==1)
        {
            cout<<1<<"\n";
        }
        else
        {
            cout<<rez[i/2]<<"\n";
        }
    }
    return 0;
}

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