QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138331#5502. Dazzling MountainFlamireWA 3020ms43792kbC++141.0kb2023-08-11 15:08:052023-08-11 15:08:05

Judging History

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

  • [2023-08-11 15:08:05]
  • 评测
  • 测评结果:WA
  • 用时:3020ms
  • 内存:43792kb
  • [2023-08-11 15:08:05]
  • 提交

answer

#include <bits/stdc++.h>
#define N 1000011
using namespace std;
int t,n,dfn[N],ed[N],clk,siz[N];vector<int> v[N];
struct edge{int v,next;edge(){}edge(int _v,int _next){v=_v;next=_next;}}e[N*2];int head[N],sz;
void init(){memset(head,-1,sizeof(head));sz=0;}void insert(int u,int v){e[++sz]=edge(v,head[u]);head[u]=sz;}
void dfs(int u,int f)
{
	int ch=0;siz[u]=1;dfn[u]=clk+1;
	for(int i=head[u];~i;i=e[i].next)if(e[i].v^f)dfs(e[i].v,u),siz[u]+=siz[e[i].v],++ch;
	if(!ch)dfn[u]=++clk;
	ed[u]=clk;
	v[siz[u]].push_back(u);
}
vector<int> res;
int main()
{
	scanf("%d",&t);while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;++i)head[i]=-1;sz=0;
		for(int i=1;i<=clk;++i)v[i].clear();clk=0;
		for(int i=1;i<n;++i){int u,v;scanf("%d%d",&u,&v);insert(u,v);insert(v,u);}
		dfs(1,0);res.clear();
		for(int i=1;i<=n;++i)
		{
			int cnt=0;
			for(int x:v[i])cnt+=ed[x]-dfn[x]+1;
			if(cnt==clk)res.push_back(i);
		}
		printf("%d\n",int(res.size()));
		for(int x:res)printf("%d ",x);putchar(10);
	}return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 34604kb

input:

1
9
1 2
2 3
3 4
3 5
2 6
6 7
7 8
7 9

output:

4
1 3 8 9 

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 3020ms
memory: 43792kb

input:

10000
906
675 189
555 889
491 97
791 419
175 694
713 842
788 513
159 354
670 815
652 546
253 87
89 278
563 429
522 900
202 657
331 865
35 605
735 532
612 471
657 386
7 886
856 164
224 777
73 534
481 631
711 698
240 465
115 181
191 825
311 155
709 501
207 849
294 546
591 682
96 405
210 696
861 13
781...

output:

63
1 3 4 34 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 
6
1 2 3 4 5 11 
8
1 2 6 94 95 96 98 99 
8
1 67 92 1...

result:

wrong answer 5th lines differ - expected: '28', found: '8'