Submission #1014981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014981		LeonidCuk	Village (BOI20_village)	C++17	50 / 100	64 ms	15780 KiB

Village

#include <bits/stdc++.h>
using namespace std;
vector<int>g[100000],sz(100000),vmin(100000),vmax(100000),temp,temp1;
int n;
long long int resmax=0,resmin=0;
void dfsmax(int a,int b,int c)
{
    if(c==0)
        {
            temp.push_back(a);
        }
        else if(c==2)
        {
            temp1.push_back(a);
        }
    for(auto i:g[a])
    {
        if(i!=b&&c==1)
        {
            dfsmax(i,a,c);
            resmax+=(2*min(sz[i],n-sz[i]));
        }
        else if(i!=b)
        {
            dfsmax(i,a,c);
        }
    }

}
void dfsmin(int a,int b)
{
    for(auto i:g[a])
    {
        if(i!=b)
        {
            dfsmin(i,a);
            if(vmin[i]==i)
            {
                swap(vmin[i],vmin[a]);
                resmin+=2;
            }
        }
    }
}
void dfs(int a,int b)
{
    sz[a]=1;
    for(auto i:g[a])
    {
        if(i!=b)
        {
            dfs(i,a);
            sz[a]+=sz[i];
        }
    }
}
int findcen(int a)
{
    int b=a;
    while(true)
    {
        bool check=true;
        for(auto i:g[a])
        {
            if(i!=b&&sz[i]*2>n)
            {
                b=a;
                a=i;
                check=false;
                break;
            }
        }
        if(check)
        {
            break;
        }
    }
    return a;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int a,b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        vmax[i]=i;
        vmin[i]=i;
    }
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0,0);
    int cen=findcen(0);
    dfs(cen,cen);
    a=-1;b=-1;
    dfsmin(cen,cen);
    dfsmax(cen,cen,1);
    for(auto i:g[cen])
    {
        if(sz[i]>b)
        {
            b=sz[i];
            a=i;
        }
    }
    dfsmax(a,cen,0);
    for(auto i:g[cen])
    {
        if(i!=a)
        {
           dfsmax(i,cen,2);
        }
    }
    if(temp.size()>temp1.size())temp1.push_back(cen);
    else{temp.push_back(cen);}
    for(int i=0;i<min(temp.size(),temp1.size());i++)
    {
        vmax[temp1[i]]=temp[i];
        vmax[temp[i]]=temp1[i];
    }
    if(vmax[cen]==cen)
    {
        vmax[cen]=vmax[g[cen][0]];
        vmax[g[cen][0]]=cen;
    }
    if(vmin[cen]==cen)
    {
        swap(vmin[cen],vmin[g[cen][0]]);
        resmin+=2;
    }
    cout<<resmin<<" "<<resmax<<"\n";
    for(int i=0;i<n;i++)
    {
        cout<<vmin[i]+1<<" ";
    }
    cout<<"\n";
    for(int i=0;i<n;i++)
    {
        cout<<vmax[i]+1<<" ";
    }
    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  122 |     for(int i=0;i<min(temp.size(),temp1.size());i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50