#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 11;
const int INF = (1LL << 60);
bool vis[MAXN];
vector<int> G[MAXN];
template<class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int d[51][51];
int n;
void dijkstra(int s, int ans[]){
fill(ans, ans + n, INF);
fill(vis, vis + n, false);
ans[s] = 0;
min_priority_queue<pair<int, int>> pq; pq.push({0, s});
while(!pq.empty()){
auto [dis, v] = pq.top(); pq.pop();
if(vis[v]) continue; vis[v] = true;
for(auto u : G[v]){
if(ans[u] > ans[v] + 1){
ans[u] = ans[v] + 1;
pq.push({ans[u], u});
}
}
}
}
void naive_dist(){
for(int i = 0; i < n; i++){
dijkstra(i, d[i]);
}
}
int naive_min(){
int p[10]; for(int i = 0; i < n; i++) p[i] = i;
int min_dist = INF;
do{
bool fail = false;
for(int i = 0; i < n; i++) if(p[i] == i) fail = true;
if(fail) continue;
int dist = 0; for(int i = 0; i < n; i++) dist += d[i][p[i]];
min_dist = min(min_dist, dist);
}while(next_permutation(p, p + n));
return min_dist;
}
int naive_max(){
int p[10]; for(int i = 0; i < n; i++) p[i] = i;
int max_dist = -INF;
do{
bool fail = false;
for(int i = 0; i < n; i++) if(p[i] == i) fail = true;
if(fail) continue;
int dist = 0; for(int i = 0; i < n; i++) dist += d[i][p[i]];
max_dist = max(max_dist, dist);
}while(next_permutation(p, p + n));
return max_dist;
}
int32_t main(){
cin >> n;
for(int i = 0; i < n - 1; i++){
int u, v; cin >> u >> v; u--; v--;
G[u].push_back(v); G[v].push_back(u);
}
naive_dist();
int d_min = naive_min(), d_max = naive_max();
cout << d_min << ' ' << d_max << endl;
for(int i = 0; i < n; i++){
cout << 1 << ' ';
}
cout << '\n';
for(int i = 0; i < n; i++){
cout << 1 << ' ';
}
cout << '\n';
}
Compilation message
Village.cpp: In function 'void dijkstra(long long int, long long int*)':
Village.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
21 | auto [dis, v] = pq.top(); pq.pop();
| ^
Village.cpp:22:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
22 | if(vis[v]) continue; vis[v] = true;
| ^~
Village.cpp:22:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
22 | if(vis[v]) continue; vis[v] = true;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
