Submission #951589

#	Time	Username	Problem	Language	Result	Execution time	Memory
951589		temmieowo	Village (BOI20_village)	C++17	12 / 100	39 ms	604 KiB

Village

#include <bits/stdc++.h>
#define int long long
#define fastio ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

const int MAX_N = 10+10;
const int INF = 2e18;

int n;
int a, b;
vector<vector<int>> G(MAX_N);
vector<vector<int>> dis(MAX_N, vector<int>(MAX_N));

void dfs(int start, int now, int pre){
    if (pre!=-1) dis[start][now] = dis[start][pre]+1;

    for (auto x : G[now]){
        if (x!=pre){
            dfs(start, x, now);
        }
    }
    return;
}

void solve1(){

    // input
    cin >> n;
    for (int i=0 ; i<n-1 ; i++){
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // init
    vector<int> v;
    for (int i=0 ; i<n ; i++){
        v.push_back(i);
        dfs(i, i, -1);
    }
    // for (int i=0 ; i<n ; i++){
    //     for (int j=0 ; j<n ; j++){
    //         cerr << dis[i][j] << " ";
    //     }
    //     cerr << "\n";
    // }
    // return;

    // process
    int ma = -INF, mi = INF;
    vector<int> ma_ans, mi_ans;
    do{
        int total = 0;
        for (int i=0 ; i<n ; i++){
            if (i==v[i]) goto flag;
            total += dis[i][v[i]];
        }

        if (total>ma){
            ma = total;
            ma_ans = v;
        }
        if (total<mi){
            mi = total;
            mi_ans = v;
        }

        flag:;
    } while (next_permutation(v.begin(), v.end()));

    cout << mi << " " << ma << "\n";
    for (auto x : mi_ans){
        cout << x+1 << " ";
    }
    cout << "\n";
    for (auto x : ma_ans){
        cout << x+1 << " ";
    }
    cout << "\n";

    return;
}

signed main(){

    fastio;

    int t = 1;
    while (t--){
        solve1();
    }

    return 0;
}

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