QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410205#6745. Delete the Treelzx2017WA 1ms5900kbC++201.6kb2024-05-13 18:33:422024-05-13 18:33:43

Judging History

你现在查看的是最新测评结果

  • [2024-05-13 18:33:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5900kb
  • [2024-05-13 18:33:42]
  • 提交

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