QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#157599#7107. Chaleurucup-team206#AC ✓676ms20924kbC++171.1kb2023-09-02 15:36:062023-09-02 15:36:06

Judging History

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

  • [2023-09-02 15:36:06]
  • 评测
  • 测评结果:AC
  • 用时:676ms
  • 内存:20924kb
  • [2023-09-02 15:36:06]
  • 提交

answer

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

const int N=1e5+1e3+7;

int T,n,m;

vector<int> g[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			g[i].clear();
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		set<int>c,e;
		vector<int>id;
		for(int i=1;i<=n;i++)
			id.push_back(i);
		sort(id.begin(),id.end(),[&](const int &a,const int &b) {
			return g[a].size()>g[b].size();
		});
		for(auto x:id)
		{
			int t=0;
			for(auto v:g[x])
				if(c.count(v))
					t++;
			if(t==c.size())
				c.insert(x);
			else
				break;
		}
		for(int i=1;i<=n;i++)
			if(!c.count(i))
				e.insert(i);
		int ans=1;
		for(auto x:e)
		{
			int t=0;
			for(auto v:g[x])
				if(c.count(v))
					t++;
			if(t==(int)c.size()-1)
				ans++;
		}
		printf("%d ",ans);
		map<int,int>cs;
		for(auto x:c)
		{
			int t=0;
			for(auto v:g[x])
				if(e.count(v))
					t++;
			cs[t]++;
		}
		if(cs[0])
			ans=cs[0];
		else
			ans=cs[1]+1;
		printf("%d\n",ans);
	}
}

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

詳細信息

Test #1:

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

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: 676ms
memory: 20924kb

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