oj.uz

Submission #72014

# Submission time Handle Problem Language Result Execution time Memory
72014 2018-08-26T04:42:28 Z Lawali(#2160, kig9981) Island Traversal (FXCUP3_island) C++17
0 / 100
 8 ms 7600 KB 
#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 (parent[ans.back()] == ans[0] || parent[ans[0]] == ans.back()) {
			for (int i = ans.size() - 1; i > 0; i -= 2) {
				swap(ans[i], ans[i - 1]);
				if (parent[ans[i - 2]] != ans[i - 1] && parent[ans[i - 1]] != ans[i - 2]) break;
			}
		}
		if (!ans.empty()) ans.push_back(ans[0]);
		reverse(ans.begin(), ans.end());
		cout << ans.size() - 1 << '\n';
		for (auto a : ans) {
			cout << a + 1 << ' ';
		}
		cout << '\n';
	}
	return 0;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Correct
2 Correct 8 ms 7424 KB Correct
3 Incorrect 7 ms 7600 KB Wrong
4 Halted 0 ms 0 KB -

Subtask #2
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Correct
2 Correct 8 ms 7424 KB Correct
3 Incorrect 7 ms 7600 KB Wrong
4 Halted 0 ms 0 KB -