QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127040#6634. Central Subset45645A#WA 8ms9808kbC++142.0kb2023-07-19 12:32:582023-07-19 12:33:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 12:33:01]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:9808kb
  • [2023-07-19 12:32:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	char ch;
	while((ch=getchar())<'0'||ch>'9');
	int res=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
	return res;
}	
const int N=200100;
struct Edge{
	int nxt,to;
}e[N<<1];
int h[N],e_num;
void add(int from,int to)
{
	e[++e_num].nxt=h[from];
	e[e_num].to=to;
	h[from]=e_num;
}
int n,K;
struct BCJ{
	int f[N];
	void pre()
	{
		for(int i=1;i<=n;i++) 
			f[i]=i;
	}
	int find(int x){ return f[x]==x?x:(f[x]=find(f[x])); }
	bool mrge(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y) return 0;
		f[x]=y;
		return 1;
	}
}B;
int vis[N],nxt[2][N],cnt[2],now;
int rt,mx,siz[N],all;
void getall(int u,int fa)
{
	all++;siz[u]=1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(vis[v]||v==fa) continue;
		getall(v,u);
		siz[u]+=siz[v];
	}
}
void dfs(int u,int fa)
{
	int tmp=0;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(vis[v]||v==fa) continue;
		dfs(v,u);
		if(siz[v]>tmp) tmp=siz[v];
	}
	if(all-siz[u]>tmp) tmp=all-siz[u];
	if(tmp<mx) rt=u,mx=tmp;
}
void dfs_vis(int u,int dep)
{
	if(dep>K) return void(nxt[now^1][++cnt[now^1]]=u);
	vis[u]=1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(vis[v]) continue;
		dfs_vis(v,dep+1);
	}
}
int res[N],ans;
int main()
{
	int T=read();
	while(T--)
	{
		n=read();
		int m=read();
		B.pre();
		e_num=0;
		ans=0;
		for(int i=1;i<=n;i++) vis[i]=h[i]=0;
		for(int i=1;i<=m;i++)
		{
			int u=read(),v=read();
			if(B.mrge(u,v)) add(u,v),add(v,u);
		}
		K=sqrt(n);
		if(K*K!=n) K++;
		nxt[now=0][cnt[0]=1]=1;
		while(cnt[now])
		{
			cnt[now^1]=0;
			for(int i=1;i<=cnt[now];i++)
			{
				all=0;
				getall(nxt[now][i],0);
				rt=nxt[now][i],mx=all;	
				dfs(nxt[now][i],0);
				res[++ans]=rt;
				dfs_vis(rt,0);
			}
			now^=1;	
		}
		if(ans>K) printf("-1\n");
		else
		{
			printf("%d\n",ans);
			for(int i=1;i<=ans;i++) printf("%d ",res[i]);
			printf("\n");
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9808kb

input:

2
4 3
1 2
2 3
3 4
6 7
1 2
2 3
3 1
1 4
4 5
5 6
6 4

output:

1
3 
1
4 

result:

ok correct (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 8ms
memory: 9752kb

input:

10000
15 14
13 12
5 4
9 8
11 12
15 14
10 9
14 13
2 3
2 1
6 5
10 11
3 4
7 6
8 7
6 5
2 1
2 4
4 6
2 3
3 5
10 9
8 3
9 4
5 6
5 10
3 2
5 4
2 7
1 2
4 3
2 1
2 1
2 1
2 1
9 8
9 8
5 4
1 2
6 5
3 4
3 2
7 8
7 6
2 1
1 2
14 13
3 10
5 6
2 9
11 4
2 3
2 1
8 7
13 6
5 4
5 12
6 7
4 3
7 14
16 15
2 3
2 1
6 10
6 9
6 4
9 11
...

output:

3
8 2 14 
1
2 
1
4 
1
2 
1
2 
3
5 9 1 
1
2 
1
5 
2
6 16 
1
2 
3
11 3 19 
1
4 
1
4 
1
8 
1
2 
3
8 14 2 
1
2 
1
2 
1
4 
1
2 
1
3 
1
3 
1
5 
1
5 
1
2 
3
8 2 14 
1
2 
1
5 
1
2 
1
2 
3
11 19 3 
1
3 
1
5 
2
6 16 
1
2 
1
4 
1
3 
1
4 
3
5 20 21 
1
2 
3
7 1 12 
1
2 
1
4 
1
3 
1
2 
2
6 1 
1
3 
1
4 
1
5 
1
2 
...

result:

wrong answer Integer -1 violates the range [1, 4] (test case 1829)