QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153195#7107. ChaleurPhantomThreshold#AC ✓167ms16672kbC++201.8kb2023-08-29 16:37:442023-08-29 16:37:45

Judging History

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

  • [2023-08-29 16:37:45]
  • 评测
  • 测评结果:AC
  • 用时:167ms
  • 内存:16672kb
  • [2023-08-29 16:37:44]
  • 提交

answer

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

const int maxn=100000;
int n,m;
int deg[maxn+50];
vector<int> g[maxn+50];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	for (;T--;){
		cin >> n >> m;
		for (int i=1;i<=m;i++){
			int x,y;
			cin >> x >> y;
			g[x].push_back(y);
			g[y].push_back(x);
			deg[x]++;
			deg[y]++;
		}
		int ans1=0,ans2=0;
		{
			vector<int> ok(n+5);
			vector<int> order(n+5);
			for (int i=1;i<=n;i++) order[i]=i;
			sort(order.begin()+1,order.begin()+n+1,
				[&](int x,int y){
					return deg[x]>deg[y];	
				}
			);
			int okcnt=0;
			for (int i=1;i<=n;i++){
				int u=order[i];
				int cnt=0;
				for (auto v:g[u]) if (ok[v]) cnt++;
			//	cout << "u,cnt : " << u << " " << cnt << endl;
				if (cnt!=okcnt) continue;
				ok[u]=1;
				okcnt++;
			}
			int ans=1;
			for (int i=1;i<=n;i++) if (!ok[i]){
				int cnt=0;
				for (auto v:g[i]) if (ok[v]) cnt++;
				if (cnt==okcnt-1) ans++;
			}
			ans1=ans;
		//	cout << "okcnt : " << okcnt << endl;
		//	for (int i=1;i<=n;i++) cout << ok[i] << " ";
		//	cout << endl;
		}
		{
			vector<int> ok(n+5);
			vector<int> order(n+5);
			for (int i=1;i<=n;i++) order[i]=i;
			sort(order.begin()+1,order.begin()+n+1,
				[&](int x,int y){
					return deg[x]<deg[y];	
				}
			);
			int okcnt=0;
			for (int i=1;i<=n;i++){
				int u=order[i];
				int cnt=okcnt;
				for (auto v:g[u]) if (ok[v]) cnt--;
				if (cnt!=okcnt) continue;
				ok[u]=1;
				okcnt++;
			}
			int ans=1;
			for (int i=1;i<=n;i++) if (!ok[i]){
				int cnt=okcnt;
				for (auto v:g[i]) if (ok[v]) cnt--;
				if (cnt==okcnt-1) ans++;
			}
			ans2=ans;
		}
	//	cout << "--- :: ";
		cout << ans1 << " " << ans2 << "\n";
		for (int i=1;i<=n;i++){
			g[i].clear();
			deg[i]=0;	
		}
	}
	return 0;	
}

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

詳細信息

Test #1:

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

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: 167ms
memory: 16672kb

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