Submission #71995

#	Time	Username	Problem	Language	Result	Execution time	Memory
71995		Lawali (#118)	Island Traversal (FXCUP3_island)	C++17	0 / 100	8 ms	7452 KiB

island

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

vector<int> adj[300000], parent, sel, depth;
priority_queue<pair<int, int>> Q;

void dfs(int c)
{
	bool leaf = true;
	for (auto n : adj[c]) {
		if (n != parent[c]) {
			depth[n] = depth[c] + 1;
			parent[n] = c;
			dfs(n);
			leaf = false;
		}
	}
	if (leaf) Q.push({ depth[c],c });
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	int N;
	vector<int> ans;
	cin >> N;
	parent.resize(N, -1);
	sel.resize(N, -1);
	depth.resize(N);
	for (int i = 1; i < N; i++) {
		int a, b;
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
	parent[0] = 0;
	dfs(0);
	while (!Q.empty()) {
		int c = Q.top().second;
		Q.pop();
		if (c == 0 || sel[c] != -1 || sel[parent[c]] != -1) continue;
		sel[c] = parent[c];
		sel[parent[c]] = c;
		Q.push({ depth[parent[parent[c]]],parent[parent[c]] });
	}
	for (int i = 0; i < N; i++) {
		if (sel[i] != -1 && i < sel[i]) {
			if (ans.empty() || parent[ans.back()] != i && parent[i] != ans.back()) {
				ans.push_back(i);
				ans.push_back(sel[i]);
			}
			else {
				ans.push_back(sel[i]);
				ans.push_back(i);
			}
		}
	}
	if (ans.size() <= 2) {
		cout << "0\n";
	}
	else {
		if (!ans.empty()) ans.push_back(ans[0]);
		reverse(ans.begin(), ans.end());
		cout << ans.size() << '\n';
		for (auto a : ans) {
			cout << a + 1 << ' ';
		}
		cout << '\n';
	}
	return 0;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:58:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if (ans.empty() || parent[ans.back()] != i && parent[i] != ans.back()) {

• Subtask 1: 0 / 42
• Subtask 2: 0 / 58