QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202474 | #6745. Delete the Tree | real_sigma_team | WA | 1ms | 3560kb | C++23 | 1.9kb | 2023-10-06 04:39:53 | 2023-10-06 04:39:53 |
Judging History
answer
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<vector<bool>> adj(n, vector<bool>(n));
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u][v] = adj[v][u] = 1;
}
vector<vector<int>> ans;
vector<int> del(n);
for (int i = 0; i < 10; ++i) {
int prev = 0;
for (int j = 0; j < n; ++j) prev += del[j] == 0;
ans.push_back({});
vector<int> c0, c1;
vector<int> col(n, 0);
auto dfs = [&](auto dfs, int u, int p) -> void {
if (del[u] == 0) {
if (col[u] == 0) c0.push_back(u);
else c1.push_back(u);
}
for (int to = 0; to < n; ++to) {
if (adj[u][to] && to != p) {
col[to] = col[u] ^ (1 ^ del[to]);
dfs(dfs, to, u);
}
}
};
dfs(dfs, rnd() % n, -1);
if (c0.size() < c1.size()) swap(c0, c1);
for (auto j : c0) {
for (auto k : c0) {
assert(adj[j][k] == 0);
}
}
for (auto j : c0) {
ans.back().push_back(j);
del[j] = 1;
}
int now = 0;
for (int j = 0; j < n; ++j) now += del[j] == 0;
assert(now * 2 <= prev);
}
while (ans.back().empty()) ans.pop_back();
cout << ans.size() << '\n';
for (auto i : ans) {
cout << i.size();
for (auto j : i) cout << ' ' << j + 1;
cout << '\n';
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3560kb
input:
5 1 2 1 3 1 4 4 5
output:
2 3 4 2 3 2 1 5
result:
wrong answer