Submission #1135271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135271		alir3za_zar3	Village (BOI20_village)	C++20	100 / 100	135 ms	87356 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,Lo,Hi=0 , lo[N],hi[N],sz[N],so[N],k[N];
deque<pair<int,int>> q[N];
vector<int> e[N];

int root (int v)
{ return k[v]==v ? v:k[v]=root(k[v]); }

void Union (int u , int v , int d)
{
    v=root(v); u=root(u);
    if (so[v]<so[u]){ swap(v,u); }
    k[u]=v;
    loop(i,0,so[u]-1)
    {
        q[v].push_back({q[u].front().first,d});
        q[v].push_back({q[v].front().first,d});
        swap(hi[q[u].front().first],
             hi[q[v].front().first]);
        q[u].pop_front(); 
        q[v].pop_front();
    } 
    so[v] += so[u];
    q[u].shrink_to_fit();
}

void brain_DFS (int v , int p , int d)
{
    sz[v] = 1; 
    for (auto to : e[v])
    {
        if (to == p){ continue; }
        brain_DFS(to,v,d+1); Union(v,to,d);
        sz[v] += sz[to];
        Hi += min(sz[to],n-sz[to]);
    }
    if (lo[v] == v)
    {
        if (v==p)
            swap(lo[v],lo[e[v].front()]);
        else 
            swap(lo[v],lo[p]);
        Lo += 2;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
 
    cin >> n;
    loop(i,1,n)
    { 
        lo[i] = hi[i] = k[i] = i; 
        so[i]=1; q[i].push_back({i,n+5});
    }
    loop(i,1,n-1)
    {
        int u,v; cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    brain_DFS(1,1,0);
    cout << Lo << " " << 2*Hi << '\n';
    loop(i,1,n){ cout << lo[i] << " "; }
    cout << '\n';
    loop(i,1,n){ cout << hi[i] << " "; }
    cout << '\n';
}

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