QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412992 | #6745. Delete the Tree | Savior | WA | 1ms | 3456kb | C++20 | 1.4kb | 2024-05-16 23:18:25 | 2024-05-16 23:18:25 |
Judging History
answer
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
#define int long long
using ll = long long;
const int inf = 1e17+7;
const int N=505;
const int mod =1e9+7;
typedef pair<int,int>P;
int mn=inf,rt=0,n=0;
int tot=0;
int sz[N];
vector<int>ans[N];
int vis[N],mx[N];
vector<int>e[N];
void get(int u,int fa){
sz[u]=1;mx[u]=0;
for(auto v:e[u]){
if(v==fa||vis[v]) continue;
get(v,u);
mx[u]=max(mx[u],sz[v]);
sz[u]+=sz[v];
}
mx[u]=max(mx[u],n-sz[u]);
if(mx[u]<mx[rt]) rt=u;
return;
}
void dfs(int u,int fa,int w){
if(vis[u]) return;
ans[w].push_back(u);
tot=max(tot,w);
vis[u]=1;
for(auto v:e[u]){
if(v==fa||vis[v]) continue;
mn=inf;
if(sz[u]>sz[v])n=sz[v];
else n=sz[u]-sz[v];
get(v,u);
dfs(rt,0,w+1);
}
}
void solve(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
get(1,0);
dfs(rt,0,1);
cout<<tot<<endl;
for(int i=tot;i>=0;i--){
cout<<ans[i].size()<<' ';
for(auto it:ans[i])
cout<<it<<' ';
cout<<endl;
}
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t=1;//cin>>t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3456kb
input:
5 1 2 1 3 1 4 4 5
output:
1 1 0 0
result:
wrong answer Integer 0 violates the range [1, 5]