QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #397121 | #6745. Delete the Tree | skulker | WA | 2ms | 7976kb | C++20 | 2.6kb | 2024-04-23 17:05:02 | 2024-04-23 17:05:03 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<int> nex[200010];
vector<int> ed[200010];
int siz[200010];
int max_son[200010];
bool del[200010];
int now_sz;
int d[200010];
int dis[200010];
int mp[10000010];
int cnt;
int q[200010];
int tot=0;
vector<int> ans[200010];
void get_dis(int now,int from){
d[++cnt] =dis[now];
if(dis[now]%2==0){
del[now]=1;
ans[tot].push_back(now);
for(int i=0;i<nex[now].size();i++)
for(int j=i+1;j<nex[now].size();j++){
int u=nex[now][i];
int v=nex[now][j];
nex[u].push_back(v);
nex[v].push_back(u);
}
}
for(int i=0;i<nex[now].size();i++){
int y= nex[now][i];
if(y==from) continue ;
if(del[y]==1) continue ;
dis[y]=dis[now]+ed[now][i];
get_dis(y,now);
}
}
void calc(int now,int from){
ans[++tot].push_back(now);
mp[0]=1;
dis[now]=0;
for(int i=0;i<nex[now].size();i++){
int y=nex[now][i];
if(del[y]==1) continue ;
if(y==from) continue ;
cnt=0;
dis[y]=ed[now][i];
get_dis(y,now);
}
}
int root=0;
void fi(int now,int from){
//找重心
siz[now]=1;
max_son[now]=0;
for(int i=0;i<nex[now].size();i++){
int y=nex[now][i];
if(del[y]==1) continue ;
if(y==from) continue ;
fi(y,now);
siz[now]+=siz[y];
dis[y]=dis[now]+ed[now][i];
max_son[now]=max(max_son[now],siz[y]);
}
max_son[now]=max(max_son[now],now_sz-siz[now]);
if(max_son[now]<max_son[root]){
root=now;
}
}
void dfz(int now ,int from){
// printf("root=%d\n",root);
del[now]=1;
calc(now,from);
//计算当前点
for(int i=0;i<nex[now].size();i++){
int y= nex[now][i];
if(del[y]==1) continue ;
if(y==from )continue ;
max_son[0]=10000000;
now_sz=siz[y];
root=0;
fi(y,0);
dfz(root,now);
}
}
int main(){
scanf("%d",&n);
int u,v,w;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
w=1;
nex[u].push_back(v);
ed[u].push_back(w);
nex[v].push_back(u);
ed[v].push_back(w);
}
root=0;
max_son[0]=10000000;
now_sz=n;
fi(1,0);
// printf("init root=%d\n",root);
dfz(root,0);
printf("%d\n", tot);
for(int i=1;i<=tot;i++){
printf("%d ",ans[i].size());
for(int j=0;j<ans[i].size();j++){
printf("%d ",ans[i][j]);
}
printf("\n");
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 7976kb
input:
5 1 2 1 3 1 4 4 5
output:
4 2 1 5 1 2 1 3 1 4
result:
ok
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 6144kb
input:
500 183 443 32 443 334 443 254 443 331 443 348 443 54 443 430 443 275 443 410 443 360 443 443 468 140 443 179 443 93 443 327 443 128 443 365 443 122 443 43 443 46 443 399 443 398 443 269 443 130 443 227 443 412 443 61 443 295 443 98 443 30 443 197 443 397 443 95 443 192 443 266 443 48 443 310 443 28...
output:
500 1 443 1 183 1 32 1 334 1 254 1 331 1 348 1 54 1 430 1 275 1 410 1 360 1 468 1 140 1 179 1 93 1 327 1 128 1 365 1 122 1 43 1 46 1 399 1 398 1 269 1 130 1 227 1 412 1 61 1 295 1 98 1 30 1 197 1 397 1 95 1 192 1 266 1 48 1 310 1 283 1 127 1 123 1 7 1 154 ...
result:
wrong answer Integer 500 violates the range [0, 10]