Submission #827805

#	Time	Username	Problem	Language	Result	Execution time	Memory
827805		QwertyPi	Village (BOI20_village)	C++14	50 / 100	1084 ms	10016 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];
int c_max[MAXN], c_min[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;
}

int counter = 0;
void dfs_min(int v, int pa = -1){
	for(auto u : G[v]){
		if(u == pa) continue;
		dfs_min(u, v);
		if(c_min[u] == u) swap(c_min[u], c_min[v]), counter += 2;
	}
	if(pa == -1 && c_min[v] == v){
		for(auto u : G[v]){
			if(u == pa) continue;
			swap(c_min[u], c_min[v]), counter += 2;
			break;
		}
	}
}

int clever_min(){
	for(int i = 0; i < n; i++) c_min[i] = i;
	counter = 0;
	dfs_min(0);
	return counter;
}

int sz[MAXN], p[MAXN];
void dfs_max(int v, int pa = -1){
	sz[v] = 1;
	for(auto u : G[v]){
		if(u == pa) continue;
		dfs_max(u, v); p[u] = v; sz[v] += sz[u];
	}
}

int centroid(int v, int pa = -1){
	for(auto u : G[v]){
		if(u == pa) continue;
		if(sz[u] >= (n + 1) / 2) return centroid(u, v);
	}
	return v;
}

vector<int> ST[MAXN];
void dfs_st(int s, int v, int pa = -1){
	for(auto u : G[v]){
		if(u == pa) continue;
		dfs_st(s, u, v);
	}
	ST[s].push_back(v);
}

int clever_max(){

	dfs_max(0);
	int c = centroid(0);
	dfs_max(c);
	int s = 0;
	for(int i = 0; i < n; i++){
		s += min(sz[i], n - sz[i]) * 2;
	}
	priority_queue<pair<int, int>> pq;
	for(auto v : G[c]){
		dfs_st(v, v, c); pq.push({sz[v], v});
	}

	int prv = -1;
	vector<int> ord {c};
	while(!pq.empty()){
		auto [s, v] = pq.top(); pq.pop();
		int u = ST[v][sz[v] - 1]; sz[v]--;
		ord.push_back(u);
		if(prv != -1 && sz[prv] > 0) pq.push({sz[prv], prv});
		prv = v;
	}
	for(int i = 0; i < n; i++){
		c_max[ord[i]] = ord[(i + 1) % n];
	}

	for(int i = 0; i < n; i++){
		if(c_max[i] == i){
			swap(c_max[i], c_max[G[i][0]]);
		}
	}

	return s;
}

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();
	int d2_min = clever_min(), d2_max = clever_max();

	// assert(d2_min == d_min);
	// assert(d2_max == d_max);

	cout << d2_min << ' ' << d2_max << endl;
	for(int i = 0; i < n; i++) cout << c_min[i] + 1 << " \n"[i == n - 1];
	for(int i = 0; i < n; i++) cout << c_max[i] + 1 << " \n"[i == n - 1];
}

Compilation message (stderr)

Village.cpp: In function 'void dijkstra(long long int, long long int*)':
Village.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |         auto [dis, v] = pq.top(); pq.pop();
      |              ^
Village.cpp:23:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |         if(vis[v]) continue; vis[v] = true;
      |         ^~
Village.cpp:23:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |         if(vis[v]) continue; vis[v] = true;
      |                              ^~~
Village.cpp: In function 'long long int clever_max()':
Village.cpp:131:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |   auto [s, v] = pq.top(); pq.pop();
      |        ^

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