QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410205 | #6745. Delete the Tree | lzx2017 | WA | 1ms | 5900kb | C++20 | 1.6kb | 2024-05-13 18:33:42 | 2024-05-13 18:33:43 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=30001;
int i,j,n,m,k,l,x,y,in[N],h[N],cnt,bz[N],dl[20][N],gs,sum,vis[N];
struct node{
int nxt,to;
}e[N*10];
void add(int u,int v)
{
e[++cnt].nxt=h[u];
e[cnt].to=v;
h[u]=cnt;
}
void dfs(int x,int father)
{
vis[x]=1;
for(int i=h[x];i;i=e[i].nxt)
if(bz[e[i].to]==0&&e[i].to!=father) dfs(e[i].to,x);
if(in[x]<=1)
{
dl[gs][0]++;
dl[gs][dl[gs][0]]=x;
bz[x]=1;
return;
}
if(in[x]==2)
{
int pd=0;
for(int i=h[x];i;i=e[i].nxt)
if(bz[e[i].to]==1)
{
pd=1;
break;
}
if(pd==0)
{
dl[gs][0]++;
dl[gs][dl[gs][0]]=x;
bz[x]=1;
return;
}
}
}
int main()
{
//freopen("1.in","r",stdin);
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
in[x]++;in[y]++;
add(x,y);
add(y,x);
}
gs=0;sum=0;
while(sum<n)
{
gs++;
for(i=1;i<=n;i++)
if(bz[i]==0) vis[i]=0;
else vis[i]=1;
for(i=1;i<=n;i++)
if(vis[i]==0)
{
dfs(i,0);
}
sum+=dl[gs][0];
for(i=1;i<=dl[gs][0];i++)
{
bz[dl[gs][i]]=2;
if(in[dl[gs][i]]==1)
{
for(j=h[dl[gs][i]];j;j=e[j].nxt)
if(bz[e[j].to]==0)in[e[j].to]--;
in[dl[gs][i]]--;
}
else
{
x=y=0;
in[dl[gs][i]]=0;
for(j=h[dl[gs][i]];j;j=e[j].nxt)
if(bz[e[j].to]==0)
{
if(x==0) x=e[j].to;
else y=e[j].to;
}
add(x,y);
add(y,x);
}
}
}
printf("%d\n",gs);
for(i=1;i<=gs;i++)
{
printf("%d ",dl[i][0]);
for(j=1;j<=dl[i][0];j++)
printf("%d ",dl[i][j]);
printf("\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5900kb
input:
5 1 2 1 3 1 4 4 5
output:
2 3 5 3 2 2 4 1
result:
wrong answer