Submission #1020248

#TimeUsernameProblemLanguageResultExecution timeMemory
1020248ali2241Village (BOI20_village)C++17
12 / 100
74 ms3664 KiB
#include <bits/stdc++.h> //ali2241 using namespace std; #define int long long //using ll = __int128; using ld = long double; const int M = 10589; const int N = 1001; vector<int> adj[N]; int dis[N][N]; int get (int a, int b, int c = -1) { if (a == b) { return 0; } int ans = -1e9; for (int i : adj[a]) { if (i != c) ans = max(ans, get(i, b, a)); } return ans + 1; } int fact(int n) { if (n == 0) return 1; return n * fact(n - 1); } void fun() { int n; cin >> n; for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } pair<int, vector<int>> mn = {1e9, {}}; pair<int, vector<int>> mx = {-1e9, {}}; vector<int> per; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dis[i][j] = get(i, j); } } for (int i = 1; i <= n; ++i) { per.push_back(i); } for (int i = 0; i < fact(n); ++i) { int ths = 0; bool b = 0; for (int i = 0; i < n; ++i) { if (i + 1 == per[i]) { b = 1; continue; } ths += dis[i + 1][per[i]]; } if (ths < mn.first and !b) { mn = {ths, per}; } if (ths > mx.first and !b) { mx = {ths, per}; } next_permutation(per.begin(), per.end()); } cout << mn.first << " " << mx.first << "\n"; for (int i = 0; i < n; ++i) { cout << mn.second[i] << " "; } cout << "\n"; for (int i = 0; i < n; ++i) { cout << mx.second[i] << " "; } } int32_t main() { // freopen("output.txt", "w", stdout); // freopen("input.txt", "r", stdin); ios::sync_with_stdio(0); int tc = 1; while (tc--) fun(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...