QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252238 | #6745. Delete the Tree | ucup-team191# | WA | 1ms | 3176kb | C++14 | 1.0kb | 2023-11-15 16:58:15 | 2023-11-15 16:58:16 |
Judging History
answer
#include <cstdio>
#include <vector>
using namespace std;
const int N = 505;
int n, cen[N], siz[N], naj;
vector < int > v[N], cv;
void dfs(int x, int lst) {
cv.push_back(x); siz[x] = 1;
for(int y : v[x]) {
if(y != lst && !cen[y]) {
dfs(y, x);
siz[x] += siz[y];
}
}
}
int nadi_centroid() {
int odg = cv[0];
for(int y : cv)
if(siz[y] < siz[odg] && 2 * siz[y] >= (int)cv.size())
odg = y;
return odg;
}
void solve(int x, int raz){
naj = max(naj, raz);
dfs(x, x);
x = nadi_centroid();
cv.clear(); cen[x] = raz;
cen[x] = raz;
for(int y : v[x])
if(!cen[y]) solve(y, raz + 1);
}
int main(){
scanf("%d", &n);
for(int i = 1;i < n;i++) {
int x, y; scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
solve(1, 1);
for(int i = naj;i >= 1;i--) {
vector < int > tko;
for(int j = 1;j <= n;j++)
if(cen[j] == i) tko.push_back(j);
printf("%d ", (int)tko.size());
for(int x : tko) printf("%d ", x);
printf("\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3176kb
input:
5 1 2 1 3 1 4 4 5
output:
1 4 3 2 3 5 1 1
result:
wrong answer