oj.uz

Submission #71995

# Submission time Handle Problem Language Result Execution time Memory
71995 2018-08-26T04:33:21 Z Lawali(#2160, kig9981) Island Traversal (FXCUP3_island) C++17
0 / 100
 8 ms 7452 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 (!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

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 7 ms 7416 KB Correct
2 Correct 8 ms 7416 KB Correct
3 Incorrect 8 ms 7452 KB Wrong
4 Halted 0 ms 0 KB -

Subtask #2
0 / 58.0

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