Submission #1307562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307562		shisp1	Village (BOI20_village)	C++20	0 / 100	934 ms	12096 KiB

Village

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define int long long
using namespace std;
const int mod = 1e9+7;
const int N = 11;
const int inf = 1e18;
int n;
vector<int>g[N];
int d[N];
int bfs(int st, int en) {
    queue<int>q;
    for(int i = 1;i<=n;i++) d[i] = inf;
    q.push(st);
    d[st] = 0;
    while(q.size()) {
        int v=q.front(); q.pop();
        for(auto to:g[v]) {
            if(d[to]>d[v]+1) {
                d[to] = d[v]+1;
                q.push(to);
            }
        }
    }
    return d[en];
}
void solve() {
    cin >> n;
    for(int i = 1;i<n;i++) {
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    int mn = 1e18;
    int mx = 0;
    vector<int>mxans, mnans;
    vector<int>p;
    for(int i = 0;i<n;i++) p.pb(i+1);
    do {
        bool ok = true;
        for(int i = 0;i<n;i++) {
            if(p[i] == i+1) {ok = false; break;}
        }
        if(!ok) continue;
        int sum = 0;
        for(int i = 0;i<n;i++) {
            sum+=bfs(i+1,p[i]);
        }
        if(sum>mx) {
            mx = sum;
            mxans = p;
        }
        if(sum<mn) {
            mn = sum;
            mnans = p;
        }
    } while(next_permutation(p.begin(),p.end()));
    cout << mn << " " << mx << "\n";
    for(auto it:mnans) {
        cout << it << " ";
    }
    cout << "\n";
    for(auto it:mxans) {
        cout << it << " ";
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--) {
        solve();
    }





    return 0;
}

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