Submission #852964

#	Time	Username	Problem	Language	Result	Execution time	Memory
852964		overwatch9	Village (BOI20_village)	C++17	12 / 100	38 ms	604 KiB

Village

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 10 + 1;
vector <int> adj[maxn];
int dis[maxn][maxn];
void dfs(int s, int p, int d, int og) {
    dis[og][s] = d;
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        dfs(i, s, d+1, og);
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0; i < n; i++)
        dfs(i, i, 0, i);
    vector <int> nums(n);
    for (int i = 0; i < n; i++)
        nums[i] = i;
    int min_path = 1e9, max_path = 0;
    vector <int> min_path_nodes, max_path_nodes;
    do {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (i == nums[i]) {
                ans = 1e9;
                break;
            }
            ans += dis[i][nums[i]];
        }
        if (ans == 1e9)
            continue;
        if (min_path > ans) {
            min_path = ans;
            min_path_nodes = nums;
        }
        if (max_path < ans) {
            max_path = ans;
            max_path_nodes = nums;
        }
    } while(next_permutation(nums.begin(), nums.end()));
    cout << min_path << ' ' << max_path << '\n';
    for (auto i : min_path_nodes)
        cout << i+1 << ' ';
    cout << '\n';
    for (auto i : max_path_nodes)
        cout << i+1 << ' ';
    cout << '\n';
}

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