Submission #827789

#	Time	Username	Problem	Language	Result	Execution time	Memory
827789		QwertyPi	Village (BOI20_village)	C++14	0 / 100	4 ms	5204 KiB

Village

#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 (stderr)

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;
      |                              ^~~

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