제출 #1135227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135227		alir3za_zar3	Village (BOI20_village)	C++20	12 / 100	26 ms	328 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 = 10+7;
int n,mn=1e18,mx=0 , q[N][N];
vector<int> e[N];

void Dfs (int v , int p , int rt , int d)
{
    q[rt][v] = d;
    for (auto to : e[v])
    {
        if (to == p){ continue; }
        Dfs(to,v,rt,d+1);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
 
    cin >> n;
    loop(i,1,n-1)
    {
        int u,v; cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    loop(i,1,n)
    {
        Dfs(i , i , i , 0);
    }
    int p[n+1],A[n+1],B[n+1];
    loop(i,1,n){ p[i]=i; }
    
    do { int vl = 0; bool mrk=0;
        loop(i,1,n)
        {
            if (p[i]==i)
            { 
                mrk=1; break; 
            }
            vl += q[i][p[i]];
        }
        if (mrk){ continue; }
        if (vl<mn)
        { 
            mn=vl; 
            loop(i,1,n){ A[i]=p[i]; }
        }
        if (vl>mx)
        { 
            mx=vl; 
            loop(i,1,n){ B[i]=p[i]; }
        }
    } while (next_permutation(p+1,p+1+n));
    cout << mn << " " << mx << '\n';
    loop(i,1,n){ cout << A[i] << " "; }
    cout << '\n';
    loop(i,1,n){ cout << B[i] << " "; }
    cout << '\n';
}

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