QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#177676 | #6745. Delete the Tree | ucup-team870 | WA | 1ms | 3512kb | C++17 | 1.2kb | 2023-09-13 09:29:57 | 2023-09-13 09:29:58 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N = 510;
vector <int> e[N], ans[N];
int sz[N], son[N], vis[N], mnsz, mxd;
void dfs(int u, int ff) {
sz[u] = 1;
son[u] = 0;
// vis[u] = 1;
for (auto v: e[u]) {
if (vis[v] || v == ff) continue;
dfs(v, u);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void divide(int u, int d) {
mxd = max(mxd, d);
dfs(u, 0);
int rt = u, tot = sz[u];
while (sz[son[rt]]*2 > tot) rt = son[rt];
vis[rt] = 1;
ans[d].push_back(rt);
for (auto v: e[rt]) {
if (!vis[v]) {
divide(v, d+1);
}
}
}
int main() {
int n; scanf("%d", &n);
rep (i, 1, n-1) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
divide(1, 0);
cout << mxd<<endl;
for (int i = mxd; i >= 0; i--) {
int len = ans[i].size();
cout << len<<' ';
rep (j, 0, len-1) {
cout << ans[i][j]<<' ';
}
cout <<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3512kb
input:
5 1 2 1 3 1 4 4 5
output:
2 1 5 3 2 3 4 1 1
result:
wrong answer