QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270547#6745. Delete the TreecciafrinoWA 0ms3892kbC++201.3kb2023-12-01 01:54:352023-12-01 01:54:35

Judging History

你现在查看的是最新测评结果

  • [2023-12-01 01:54:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3892kb
  • [2023-12-01 01:54:35]
  • 提交

answer

#include<bits/stdc++.h>

int main() {
	using namespace std;
	cin.tie(nullptr)->sync_with_stdio(false);
	int N; cin >> N;

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

	vector<bool> deleted(N);
	vector<pair<int, int>> max_sub(N);
	auto dfs = [&](auto& self, int cur, int prv) -> int {
		int sz = 1;
		max_sub[cur] = {0, -1};
		for (int nxt : adj[cur]) {
			if (nxt == prv || deleted[nxt]) continue;
			int cur_sz = self(self, nxt, cur);
			sz += cur_sz;
			max_sub[cur] = max(max_sub[cur], {cur_sz, nxt});
		}
		return sz;
	};

	int ops_num = 0;
	vector<int> level(N);
	array<vector<int>, 10> ans;
	auto rec = [&](auto& self, int cur, int prv) -> void {
		int sz = dfs(dfs, cur, -1);
		while (2*max_sub[cur].first > sz) cur = max_sub[cur].second;

		deleted[cur] = true;
		if (~prv) level[cur] = level[prv] + 1;
		ans[level[cur]].push_back(cur);
		ops_num += 1;

		for (int nxt : adj[cur]) {
			if (deleted[nxt]) continue;
			self(self, nxt, cur);
		}
	};

	rec(rec, 0, -1);

	cout << ops_num << '\n';
	for (int lvl = 9; lvl >= 0; --lvl) {
		if (ans[lvl].empty()) continue;
		cout << int(ans[lvl].size());
		for (auto v : ans[lvl]) {
			cout << ' ' << v+1;
		}
		cout << '\n';
	}
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3892kb

input:

5
1 2
1 3
1 4
4 5

output:

5
1 5
3 2 3 4
1 1

result:

wrong output format Unexpected end of file - int32 expected