Submission #1014979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014979		LeonidCuk	Village (BOI20_village)	C++17	0 / 100	2 ms	4188 KiB

Village

#include <bits/stdc++.h>
using namespace std;
vector<int>g[100000],sz(100000),vmin(100000),vmax(100000),temp,temp1,temp2(100000);
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)
{
    vector<int>t;
    for(auto i:g[a])
    {
        if(i!=b)
        {
            dfsmin(i,a);
            if(temp2[i]!=0)
            {
                t.push_back(temp2[i]-1);
            }
        }
    }
    resmin+=(2*t.size());
    t.push_back(a);
    reverse(t.begin(),t.end());
    for(int i=1;i<t.size();i+=2)
    {
        vmin[t[i]]=t[i-1];
        vmin[t[i-1]]=t[i];
    }
    if(t.size()%2==1)
    {
        temp2[a]=t[t.size()-1]+1;
    }
}
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);
    if(n%2==1)
    {
        resmin-=2;
    }
    cout<<resmin<<" "<<resmax<<"\n";
    for(int i=0;i<n;i++)
    {
        cout<<vmin[i]+1<<" ";
    }
    cout<<"\n";
    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];
    }
    for(int i=0;i<n;i++)
    {
        cout<<vmax[i]+1<<" ";
    }
    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'void dfsmin(int, int)':
Village.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=1;i<t.size();i+=2)
      |                 ~^~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:144:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  144 |     for(int i=0;i<min(temp.size(),temp1.size());i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50