Submission #1135224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135224		alir3za_zar3	Village (BOI20_village)	C++20	0 / 100	1 ms	2632 KiB

Village

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define         int          long long
#define   loop(i , l , r)    for (int i=l; i<=r; i+=1)
#define    arc(i , r , l)    for (int i=r; i>=l; i-=1)

const int N = 1e5+7;
int n,mn=0,mx=0 , A[N],s[N];
vector<int> e[N];

int mn_processor (int v , int p)
{
    int child = 0 , sz=-1 , u=0;
    vector<int> q;
    for (auto to : e[v])
    {
        if (to == p){ continue; }
        u=to;
        if (mn_processor(to,v))
        {
            child++;++sz; q.push_back(to);
        }
    }
    for (int i=0; i<=sz-1; i+=2)
    {
        A[q[i]]=q[i+1]; 
        A[q[i+1]]=q[i];
    } 
    if (child%2)
    {
        A[q.back()]=v;
        A[v]=q.back();
        s[v]=q.back();
    }
    mn += child<<1;
    if (v==1 and child%2==0)
    { 
        A[u] = v;
        A[v] = s[u];
        mn += 2; 
    }
    return (child%2==0);
}

pair<int,int> mx_processor (int v , int p)
{
    int sz = 1 , k = 1;
    for (auto to : e[v])
    {
        if (to == p){ continue; }
        auto [a,b] = mx_processor(to,v);
        sz += a; k += b;
    }
    k = min(k,n-sz);
    if (v!=1){ mx += 2*k; }
    return {sz,k};
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
 
    cin >> n; A[1]=1;
    loop(i,1,n-1)
    {
        int u,v; cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    mn_processor(1,1);
    mx_processor(1,1);
    cout << mn << " " << mx << '\n';
    loop(i,1,n){ cout << A[i] << " "; }
    cout << '\n';
    loop(i,1,n){ cout << 1 << " "; }
    cout << '\n';
}

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