Submission #1236610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236610		lopkus	Village (BOI20_village)	C++20	100 / 100	113 ms	20336 KiB

Village

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void find_mn(vector<vector<int>>& adj, ll& mn,
	vector<int>& res) {
	int n = adj.size();
	iota(begin(res), end(res), 0);
	queue<int> q;
	vector<int> d(n, -1);
	d[0] = 0;
	q.push(0);
	while (!q.empty()) {
	    int v = q.front();
	    q.pop();
	    for (auto& u : adj[v]) {
	        if (d[u] != -1) continue;
	        d[u] = d[v] + 1;
	        q.push(u);
	    }
	}
	vector<int> deg(n);
	for (int i = 0; i < n; ++i) {
		deg[i] = adj[i].size();
	    if (adj[i].size() == 1) {
	        q.push(i);
	    }
	}
	while (!q.empty()) {
	    int v = q.front();
	    q.pop();
	    for (auto& u : adj[v]) {
	    	deg[v]--;
	    	deg[u]--;
	    	if (res[u] == u && res[v] == v) {
	    		mn += 2;
	    		swap(res[u], res[v]);
	    	}
	    	if (deg[u] == 1) {
	    		q.push(u);
	    	}
	    }
	    
	}
	for (int i = 0; i < n; ++i) {
	    if (res[i] == i) {
	        bool swapped = false;
	        for (auto& g : adj[i]) {
	            if (res[g] == g) {
	                swap(res[i], res[g]);
	                mn += 2;
	                swapped = true;
	                break;
	            }
	        }
	        if (!swapped) {
	            int g = adj[i][0];
	            swap(res[i], res[g]);
	            mn += 2;
	        }
	    }
	}

}
void dfs(vector<vector<int>>& adj, ll& res, vector<int>& sz,
	vector<int>& ord, int& t, int v, int p, vector<int>& tin) {
	tin[v] = t;
	ord[t++] = v;
	for (auto& u : adj[v]) {
		if (u == p) continue;
		dfs(adj, res, sz, ord, t, u, v, tin);
		sz[v] += sz[u];
	}	
	res += 2 * min(sz[v], (int)adj.size() - sz[v]);
}
void find_mx(vector<vector<int>>& adj, ll& res,
	vector<int>& mx) {
	int n = adj.size();
	vector<int> sz(n, 1);
	vector<int> ord(n + 1);
	vector<int> tin(n);
	int t = 1;
	dfs(adj, res, sz, ord, t, 0, -1, tin);
	for (int i = 0; i < n; ++i) {
		mx[i] = ord[(tin[i] + n / 2 - 1) % n + 1];
	}
}


int main() {
	int n;
	cin >> n;
	vector<vector<int>> adj(n);
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector<int> mn(n, -1), mx(n, -1);
	ll resmn = 0;
	find_mn(adj, resmn, mn);
	ll resmx = 0;
	find_mx(adj, resmx, mx);
	cout << resmn << " " << resmx << endl;
	for (auto& u : mn) {
		cout << u + 1 << " ";
	}
	cout << "\n";
	for (auto& u : mx) {
		cout << u + 1 << " ";
	}
	cout << "\n";
}

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