Submission #915165

#	Time	Username	Problem	Language	Result	Execution time	Memory
915165		3as8	Village (BOI20_village)	C++14	12 / 100	1008 ms	856 KiB

Village

#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);

#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)

using namespace std;

void dfs(vector<vector<ll> >& graph, vector<ll>& dist, ll startIndex, ll p, ll depth = 0) {

    dist[startIndex] = depth;
    for(auto el : graph[startIndex]) {
        if(el == p) continue;

        dfs(graph, dist, el, startIndex, depth + 1);
    }
}


void solve(ll _) {

    ll n; cin>>n;

    vector<vector<ll> > graph(n);
    for(int i = 0; i < n - 1; i++) {
        ll x, y; cin>>x>>y;
        x--; y--;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    vector<vector<ll> > dist(n, vector<ll>(n, -1));

    for(int i = 0; i < n; i++) {
        dfs(graph, dist[i], i, -1);

    }


    vector<ll> arr(n);
    for(int i = 0; i < n; i++) arr[i] = i;

    vector<ll> mnA, mxA;

    ll mn = LLONG_MAX, mx = LLONG_MIN;
    do {

        bool is = true;
        for(int i = 0; i < n; i++) {
            is &= (arr[i] != i);
        }

        if(!is) continue;

        ll d = 0;
        for(int i = 0; i < n; i++) {
            d += dist[i][arr[i]];
        }

        if(mn > d) {
            mnA = arr;
        }
        if(mx < d) {
            mxA = arr;
        }

        mn = min(mn, d);
        mx = max(mx, d);

    } while(next_permutation(arr.begin(), arr.end()));


    cout<<mn<<" "<<mx<<endl;
    for(auto el : mnA) cout<<el + 1<<" ";
    cout<<endl;

    for(auto el : mxA) cout<<el + 1<<" ";
    cout<<endl;
}

int main() {
    fastIO

    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);

    ll t = 0; solve(t);
}

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