Submission #926505

#	Time	Username	Problem	Language	Result	Execution time	Memory
926505		andrei_boaca	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1036 ms	31428 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;
int n,sol[200005],par[200005],nr[200005],use[200005],reprez[200005],niv[200005];
vector<int> muchii[200005];
vector<int> nodes;
void dfs1(int nod)
{
    nr[nod]=1;
    for(int i:muchii[nod])
        if(!use[i]&&i!=par[nod])
        {
            par[i]=nod;
            dfs1(i);
            nr[nod]+=nr[i];
        }
}
void dfs(int nod)
{
    if(niv[nod]>=1)
        nodes.push_back(nod);
    nr[nod]=1;
    for(int i:muchii[nod])
        if(!use[i]&&i!=par[nod])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            if(niv[nod]==0)
                reprez[i]=i;
            else
                reprez[i]=reprez[nod];
            dfs(i);
            nr[nod]+=nr[i];
        }
}
int arb[4*200005];
void build(int nod,int st,int dr)
{
    arb[nod]=-1;
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        arb[nod]=max(arb[nod],val);
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(nod*2,st,mij,poz,val);
    else
        update(nod*2+1,mij+1,dr,poz,val);
    arb[nod]=max(arb[nod*2],arb[nod*2+1]);
}
int query(int nod,int st,int dr,int a,int b)
{
    if(st>=a&&dr<=b)
        return arb[nod];
    int mij=(st+dr)/2;
    int rez=-1;
    if(a<=mij)
        rez=max(rez,query(nod*2,st,mij,a,b));
    if(b>mij)
        rez=max(rez,query(nod*2+1,mij+1,dr,a,b));
    return rez;
}
int R;
void solve()
{
    build(1,1,nr[R]);
    for(int i=0;i<nodes.size();i++)
    {
        int j=i;
        while(j<nodes.size()&&reprez[nodes[j]]==reprez[nodes[i]])
            j++;
        j--;
        for(int k=i;k<=j;k++)
        {
            int x=nodes[k];
            int val=query(1,1,nr[R],nr[x],nr[R]);
            if(val!=-1)
                sol[2*nr[x]]=max(sol[2*nr[x]],val+niv[x]+1);
        }
        for(int k=i;k<=j;k++)
        {
            int x=nodes[k];
            update(1,1,nr[R],nr[x],niv[x]);
        }
        i=j;
    }
}
void centroid(int nod)
{
    par[nod]=0;
    dfs1(nod);
    int root=nod;
    int lg=nr[nod];
    while(true)
    {
        bool bad=0;
        for(int i:muchii[root])
            if(!use[i]&&par[i]==root&&i!=par[root]&&nr[i]>lg/2)
            {
                par[i]=0;
                par[root]=i;
                nr[root]-=nr[i];
                nr[i]+=nr[root];
                root=i;
                bad=1;
                break;
            }
        if(!bad)
            break;
    }
    R=root;
    nodes.clear();
    niv[root]=0;
    dfs(root);
    for(int i:nodes)
    {
        int x=nr[i];
        int y=nr[root]-nr[reprez[i]];
        int d=niv[i]+1;
        int poz=2*min(x,y);
        sol[poz]=max(sol[poz],d);
    }
    solve();
    reverse(nodes.begin(),nodes.end());
    solve();
    use[root]=1;
    for(int i:muchii[root])
        if(!use[i])
            centroid(i);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        sol[i]=1;
    centroid(1);
    for(int i=(n/2)*2;i>=2;i-=2)
        sol[i]=max(sol[i],sol[i+2]);
    for(int i=1;i<=n;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

Compilation message (stderr)

meetings2.cpp: In function 'void solve()':
meetings2.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<nodes.size();i++)
      |                 ~^~~~~~~~~~~~~
meetings2.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         while(j<nodes.size()&&reprez[nodes[j]]==reprez[nodes[i]])
      |               ~^~~~~~~~~~~~~

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