QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397031 | #6745. Delete the Tree | VictorYuan# | RE | 0ms | 0kb | C++14 | 1.8kb | 2024-04-23 15:48:02 | 2024-04-23 15:48:03 |
answer
#include <bits/stdc++.h>
const int maxn = 505;
int n, cnt;
std::vector<int> e[maxn], tmp[maxn];
std::vector<std::vector<int>> ans;
int del[maxn];
std::mt19937 rnd;
int getroot() {
std::vector<int> ret;
for (int i = 1; i <= n; ++i) if (e[i].size() == 1) { return i; }
if (ret.size() != 0) return ret[rnd() % ret.size()];
for (int i = 1; i <= n; ++i) if (del[i] == 0) return i;
assert(false);
}
void dfs(const int u, int pre = -1) {
for (auto v : e[u]) if (v != pre) {
dfs(v, u);
}
if (e[u].size() == 2) {
int v = e[u][0];
if (v == pre) v = e[u][1];
if (!del[v]) {
del[u] = 1;
ans.back().push_back(u);
}
} else if (e[u].size() < 2 && pre != -1) {
del[u] = 1;
ans.back().push_back(u);
} else if (e[u].size() < 2) {
if (e[u].size() == 0 || (e[u].size() == 1 && !del[e[u][0]])) {
del[u] = 1;
ans.back().push_back(u);
}
}
}
int main() {
rnd.seed(time(nullptr));
std::cin >> n;
for (int u, v, i = 1; i < n; ++i) {
std::cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
while (cnt != n) {
ans.push_back(std::vector<int>());
dfs(getroot());
for (int i = 1; i <= n; ++i) tmp[i].clear();
for (int u = 1; u <= n; ++u) if (!del[u]) {
for (auto v : e[u]) if (!del[v]) {
tmp[u].push_back(v);
}
} else if (del[u] == 1) {
for (auto v : e[u]) {
for (auto k : e[u]) if (v != k) {
tmp[v].push_back(k);
}
}
del[u] = -1;
}
for (int i = 1; i <= n; ++i) e[i].swap(tmp[i]);
cnt += ans.back().size();
}
std::cout << ans.size();
if(ans.size() - 10 >= 5) return -1;
assert(ans.size() <= 10);
for (auto &i : ans) {
std::cout << '\n' << i.size(); for (auto j : i) std::cout << ' ' << j;
}
std::cout << '\n';
}
详细
Test #1:
score: 0
Runtime Error
input:
5 1 2 1 3 1 4 4 5
output:
3