QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#270547 | #6745. Delete the Tree | cciafrino | WA | 0ms | 3892kb | C++20 | 1.3kb | 2023-12-01 01:54:35 | 2023-12-01 01:54:35 |
Judging History
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