QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209838#7107. ChaleurlingyingAC ✓147ms4484kbC++14919b2023-10-10 18:12:022023-10-10 18:12:02

Judging History

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

  • [2023-10-10 18:12:02]
  • 评测
  • 测评结果:AC
  • 用时:147ms
  • 内存:4484kb
  • [2023-10-10 18:12:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int _,n,m;
int deg[N];
bool vis[N];

bool cmp(int x,int y){return deg[x]>deg[y];}

int main()
{
	scanf("%d",&_);
	while(_--)
	{
		memset(deg,0,sizeof deg);
		memset(vis,0,sizeof vis);
		scanf("%d%d",&n,&m);
		if(!m){cout<<n<<' '<<1<<'\n';continue;}
		for(int i=1;i<=m;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			deg[x]++,deg[y]++;
		}
		vector<int> vt;
		for(int i=1;i<=n;i++)vt.push_back(i);
		sort(vt.begin(),vt.end(),cmp);
		int maxsz=0;
		for(int x:vt)
		{
			if(deg[x]>=maxsz)maxsz++,vis[x]=1;
			else break;
		}
		int ans=1;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&deg[i]==maxsz-1)
				ans++;
		cout<<ans<<' ';
		int t1=0,t2=1;
		for(int i=1;i<=n;i++)if(vis[i])
		{
			if(deg[i]==maxsz-1)t1++;
			else if(deg[i]==maxsz)t2++;
		}
		if(t1)cout<<t1;
		else cout<<t2;
		cout<<'\n';
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

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

output:

2 1
1 4
1 2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 147ms
memory: 4484kb

input:

2231
1 0
5 7
4 1
3 4
3 1
3 5
4 2
3 2
4 5
5 4
2 1
2 5
2 4
2 3
5 10
3 2
2 5
1 4
4 2
4 5
1 2
1 3
3 5
3 4
1 5
5 10
1 3
2 4
1 4
5 2
2 3
1 5
5 4
1 2
3 4
5 3
5 9
2 5
3 5
2 3
2 1
4 3
3 1
4 1
4 5
2 4
5 4
4 2
4 1
4 5
4 3
5 9
4 1
4 5
3 4
2 4
2 1
3 1
2 5
3 5
3 2
5 4
2 5
2 3
2 1
2 4
5 9
5 2
1 3
4 3
1 2
5 4
4 2
5...

output:

1 1
3 1
4 1
1 5
1 5
2 1
4 1
2 1
4 1
2 1
2 1
3 1
4 1
4 1
1 5
2 1
4 1
1 5
1 5
1 5
3 1
4 1
4 1
4 1
3 1
3 1
4 1
4 1
2 1
4 1
4 1
1 5
1 5
2 1
4 1
4 1
4 1
3 1
2 1
4 1
2 1
4 1
4 1
4 1
3 1
1 5
4 1
4 1
1 5
2 1
4 1
2 1
2 1
1 5
4 1
1 5
3 1
4 1
1 5
2 1
1 5
3 1
3 1
1 5
3 1
3 1
2 1
1 5
4 1
3 1
1 5
2 1
3 1
2 1
2 1
...

result:

ok 2231 lines

Extra Test:

score: 0
Extra Test Passed