QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#780525#6421. Degree of Spanning TreeSymbolizeWA 67ms26220kbC++172.4kb2024-11-25 11:23:272024-11-25 11:23:28

Judging History

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

  • [2024-11-25 11:23:28]
  • 评测
  • 测评结果:WA
  • 用时:67ms
  • 内存:26220kb
  • [2024-11-25 11:23:27]
  • 提交

answer

/*
	Luogu name: Symbolize
	Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=5e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int t,n,m,fa[N],f[N],times[N],dep[N];
bool vis[N];
vector<pii> G[N];
struct Graph{int u,v;}e[N];
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void dfs(int x,int Fa,int top)
{
	dep[x]=dep[Fa]+1;
	fa[x]=top;
	rep4(to,G[x])
	{
		if(to.x==Fa) continue;
		dfs(to.x,x,top);
	}
	return;
}
void getans()
{
	n=read();
	m=read();
	rep1(i,1,n) 
	{
		G[i].clear();
		fa[i]=i;
		times[i]=0;
	}
	rep1(i,1,m) vis[i]=0;
	rep1(i,1,m)
	{
		e[i].u=read();
		e[i].v=read();
		int x=find(e[i].u),y=find(e[i].v);
		if(x==y) continue;
		G[x].push_back(make_pair(y,i));
		G[y].push_back(make_pair(x,i));
		fa[x]=y;
		vis[i]=1;
		++times[e[i].u];
		++times[e[i].v];
	}
	if(n==3)
	{
		puts("No");
		return;
	}
	int rt=0; 
	rep1(i,1,n) if(times[i]>n/2) rt=i;
	fa[rt]=rt;
	rep4(to,G[rt])
	{
		f[to.x]=to.y;
		dfs(to.x,rt,to.x);
	}
	rep1(i,1,m)
	{
		if(times[rt]<=n/2) break;
		int x=find(e[i].u),y=find(e[i].v);
		if(x==y||x==rt||y==rt) continue;
		if(dep[e[i].u]>dep[e[i].v]) swap(e[i].u,e[i].v),swap(x,y);
		if(dep[e[i].u]==1&&times[e[i].u]<times[e[i].v]) swap(e[i].u,e[i].v),swap(x,y);
		fa[x]=y;
		vis[f[x]]=0;
		vis[i]=1;
		--times[x];
		--times[rt];
		++times[e[i].u];
		++times[e[i].v];
	}
	if(times[rt]>n/2) puts("No");
	else
	{
//		rep1(i,1,n) 
//		{
//			if(times[i]>n/2)
//			{
//				debug();
//				cout<<n<<' '<<m<<"\n";
//				rep1(j,1,m) cout<<e[j].u<<' '<<e[j].v<<"\n";
//			}
//		}
		puts("Yes");
		rep1(i,1,m) if(vis[i]) cout<<e[i].u<<' '<<e[i].v<<"\n";
	}
	return;
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	t=read();
	while(t--) getans();
	return 0;
}
/*
1
3 4
1 3
2 3
3 3
1 2
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 22132kb

input:

2
6 9
1 2
1 3
1 4
2 3
2 4
3 4
4 5
4 6
4 6
3 4
1 3
2 3
3 3
1 2

output:

Yes
1 2
1 3
1 4
4 5
4 6
No

result:

ok 2 cases

Test #2:

score: -100
Wrong Answer
time: 67ms
memory: 26220kb

input:

11140
10 15
9 6
5 7
6 5
2 3
7 5
7 5
3 10
9 7
5 5
9 1
7 5
2 8
7 5
4 3
6 2
9 19
3 7
3 9
2 8
2 8
3 6
5 1
1 8
8 9
8 3
4 8
5 5
3 1
4 3
1 3
8 6
1 3
7 4
4 3
8 8
12 20
10 2
5 5
2 4
3 3
3 3
5 11
9 2
5 5
7 12
11 3
3 3
3 5
5 3
3 1
4 6
7 11
6 8
4 5
6 12
6 5
8 18
4 2
4 3
2 4
2 4
4 3
4 8
2 2
6 7
2 4
6 2
1 4
8 7
4...

output:

Yes
9 6
5 7
6 5
2 3
3 10
9 1
2 8
4 3
6 2
Yes
3 7
3 9
2 8
3 6
5 1
1 8
8 9
4 8
Yes
10 2
2 4
5 11
9 2
7 12
11 3
3 1
4 6
7 11
6 8
4 5
Yes
4 2
4 3
4 8
6 7
6 2
1 4
7 5
Yes
6 5
5 7
5 9
4 3
2 9
2 3
8 7
5 1
Yes
10 2
2 6
3 2
1 9
8 10
4 6
6 1
2 5
1 7
Yes
5 7
5 4
7 1
2 6
6 7
1 3
Yes
12 3
1 13
7 8
8 2
10 6
1 6
1...

result:

wrong output format Expected integer, but "Yes" found