提出 2ef65943-9ae0-4481-9728-ba6b40a8146b

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

const int INF = 1e9;

int merge_levels(const vector<int> &child_levels)
{
	if (child_levels.empty())
		return 0;
	vector<int> v;
	for (int l : child_levels)
	{
		if (l >= INF)
			return INF;
		v.push_back(l);
	}
	if (v.size() == 1)
		return max(2, v[0] + 1);
	if (v.size() == 2)
	{
		int a = v[0], b = v[1];
		if (a == b)
			return a + 2;
		return max(a, b) + 1;
	}
	return INF;
}

int main()
{
	int N;
	if (!(cin >> N))
		return 0;
	if (N == 1)
	{
		cout << 0 << endl;
		return 0;
	}

	vector<vector<int>> adj(N);
	for (int i = 0; i < N - 1; ++i)
	{
		int u, v;
		cin >> u >> v;
		--u;
		--v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 0; i < N; ++i)
	{
		if (adj[i].size() >= 4)
		{
			cout << -1 << endl;
			return 0;
		}
	}

	vector<int> order;
	vector<int> parent(N, -1);
	stack<int> st;
	st.push(0);
	while (!st.empty())
	{
		int u = st.top();
		st.pop();
		order.push_back(u);
		for (int v : adj[u])
		{
			if (v == parent[u])
				continue;
			parent[v] = u;
			st.push(v);
		}
	}

	vector<int> dp_down(N, 0);
	vector<int> dp_up(N, 0);

	for (int i = N - 1; i >= 0; --i)
	{
		int u = order[i];
		vector<int> children;
		for (int v : adj[u])
		{
			if (v == parent[u])
				continue;
			children.push_back(dp_down[v]);
		}
		dp_down[u] = merge_levels(children);
	}

	vector<int> res(N, INF);
	for (int i = 0; i < N; ++i)
	{
		int u = order[i];

		vector<int> all_dirs;
		for (int v : adj[u])
		{
			if (v == parent[u])
				all_dirs.push_back(dp_up[u]);
			else
				all_dirs.push_back(dp_down[v]);
		}

		if (adj[u].size() <= 2)
			res[u] = merge_levels(all_dirs);

		for (int v : adj[u])
		{
			if (v == parent[u])
				continue;
			vector<int> others;
			for (int next_v : adj[u])
			{
				if (next_v == v)
					continue;
				if (next_v == parent[u])
					others.push_back(dp_up[u]);
				else
					others.push_back(dp_down[next_v]);
			}
			dp_up[v] = merge_levels(others);
		}
	}

	int ans = INF;
	for (int i = 0; i < N; ++i)
		ans = min(ans, res[i]);
	cout << (ans >= INF ? -1 : ans) << endl;

	return 0;
}

結果

問題	点数	言語	結果	実行時間	メモリ
E. Fibonacci Subtree	525	C++ (gcc)	AC	286 ms	17404 KiB

テストセット

テストセット	結果	得点	実行時間	メモリ
Sample	AC × 3	0	14 ms	8192 KiB
Subtask1	AC × 12	200	18 ms	8448 KiB
Subtask2	AC × 24	325	286 ms	17404 KiB

詳細結果

テストケース	結果	実行時間	メモリ
1_1	AC	15 ms	8192 KiB
1_2	AC	15 ms	8192 KiB
1_3	AC	18 ms	8192 KiB
1_4	AC	16 ms	8320 KiB
1_5	AC	14 ms	8064 KiB
1_6	AC	17 ms	8448 KiB
1_7	AC	14 ms	8192 KiB
1_8	AC	14 ms	8192 KiB
1_9	AC	15 ms	8192 KiB
2_1	AC	100 ms	9560 KiB
2_10	AC	18 ms	8192 KiB
2_11	AC	151 ms	12288 KiB
2_12	AC	208 ms	13440 KiB
2_2	AC	91 ms	9392 KiB
2_3	AC	111 ms	10548 KiB
2_4	AC	286 ms	17404 KiB
2_5	AC	282 ms	16304 KiB
2_6	AC	111 ms	7936 KiB
2_7	AC	183 ms	12288 KiB
2_8	AC	169 ms	13056 KiB
2_9	AC	132 ms	10384 KiB
sample_1	AC	13 ms	8192 KiB
sample_2	AC	13 ms	7936 KiB
sample_3	AC	14 ms	8192 KiB