Submission #1160518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160518		lance0	Village (BOI20_village)	C++20	0 / 100	0 ms	324 KiB

Village

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n; cin >> n;
	vector<vector<int>> graph(n);
	for (int i = 0; i < n-1; i++) {
		int x,y; cin >> x >> y;
		graph[x-1].push_back(y-1);
		graph[y-1].push_back(x-1);
	}
	//BFS with delimiter for depth tracking
	//we always root at 0
	bool vis[n] = {};
	int depth[n] = {};
	queue<int> bfs;
	stack<int> rev_bfs;
	bfs.push(0);
	bfs.push(-1);
	vis[0] = true;
	int curr_depth = 0;
	while(!bfs.empty()) {
		int x = bfs.front();
		bfs.pop();
		rev_bfs.push(x);
		if (x == -1) {
			if (!bfs.empty()) {
				bfs.push(-1);
			}
			curr_depth++;
		} else {
			for (int i = 0; i < graph[x].size(); i++) {
				if (vis[graph[x][i]] == false) {
					vis[graph[x][i]] = true;
					bfs.push(graph[x][i]);
				}
			}
			depth[x] = curr_depth;
		}
	}
	for (int i = 0; i < n; i++) {
		vis[i] = false;
	}
	int arr[n] = {};
	for (int i = 0; i < n; i++) {
		arr[i] = i;
	}
	int min = 0;
		while (!rev_bfs.empty()) {
		int x = rev_bfs.top();
		rev_bfs.pop();
		if (vis[x] == false) {
			int parent = 0;
			for (int i = 0; i < graph[x].size(); i++) {
				if (depth[graph[x][i]] < depth[x]) {
					parent = graph[x][i];
				}
			}
			vector<int> shift;
			shift.push_back(parent);
			vis[parent] = true;
			for (int i = 0; i < graph[parent].size(); i++) {
				if (depth[graph[parent][i]] > depth[parent] and vis[graph[parent][i]] == false) {
					shift.push_back(graph[parent][i]);
					vis[graph[parent][i]] = true;
				}
			}
			for (int i = 0; i < shift.size(); i++) {
				arr[shift[i]] = shift[(i+1) % shift.size()];
			}
			min += 2*(shift.size()-1);
			if (shift.size() == 1) {
				vis[parent] = false;
			}
		}
	}
	//edge case checker
	if (arr[0] == 0) {
		arr[0] = arr[graph[0][0]];
		arr[graph[0][0]] = 0;
		min += 2;
	}
	cout << min << " " << min << '\n';
	for (int i = 0; i < n; i++) {
		cout << arr[i]+1 << " ";
	}
	cout << '\n';
		for (int i = 0; i < n; i++) {
		cout << arr[i]+1 << " ";
	}
	cout << '\n';
	return 0;
}

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