Submission #1313517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313517		amloxg	Village (BOI20_village)	C++20	12 / 100	1095 ms	568 KiB

Village

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef vector<vector<int>> Graph;

void genDists(int node, int parent, vector<int> &dists, Graph const& tree){
    dists[node] = dists[parent] + 1;
    for (auto next_node : tree[node]) if (next_node != parent)
        genDists(next_node, node, dists, tree);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int nodes_num;
    cin >> nodes_num;
    Graph tree(nodes_num+1);
    for (int edge = 0; edge < nodes_num-1; ++edge){
        int node_a, node_b;
        cin >> node_a >> node_b;
        tree[node_a].push_back(node_b);
        tree[node_b].push_back(node_a);
    }

    vector<vector<int>> dists(nodes_num+1, vector<int>(nodes_num+1, -1));
    for (int node = 1; node <= nodes_num; ++node) genDists(node, 0, dists[node], tree);

    int min_res = 1e9, max_res = 0;
    vector<int> min_vec, max_vec;

    vector<int> next(nodes_num);
    for (int i = 0; i < nodes_num; ++i) next[i] = i;
    do{
        int curr_res=0;
        bool wrong = false;
        for (int node = 1; node <= nodes_num; ++node){
            if (node == next[node-1]+1) wrong = true;
            curr_res += dists[node][next[node-1]+1];
        }
        if (wrong) continue;
        
        if (curr_res < min_res){
            min_res = curr_res;
            min_vec = next;
        }
        if (curr_res > max_res){
            max_res = curr_res;
            max_vec = next;
        }
    }while(next_permutation(next.begin(), next.end()));

    cout << min_res << ' ' << max_res << '\n';
    for (auto res : min_vec) cout << res + 1 << ' ';
    cout << '\n';
    for (auto res : max_vec) cout << res + 1 << ' ';
    cout << '\n';

    return 0;
}

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