QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135098#6634. Central SubsetTeam_name#WA 25ms10832kbC++201.4kb2023-08-05 11:29:222023-08-05 11:29:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 11:29:24]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:10832kb
  • [2023-08-05 11:29:22]
  • 提交

answer

#include <bits/stdc++.h>

#define _debugVar(x) { cerr << #x << " = " << x << endl; }

using namespace std;
using LL = long long;

const int N = 2e5+5;

int n, m, k;
vector<int> e[N];
int cnt;
int par[N];
int Find(int x) { return (par[x] == x) ? x : par[x] = Find(par[x]); }

int dep[N], height[N],ans[N];
void dfs(int x, int fa)
{
	dep[x] = dep[fa]+1;
	height[x] = 0;
	for(int y : e[x]) {
		if(y == fa) continue;
		dfs(y, x);
		height[x] = max(height[x], height[y]+1);
	}
	if(height[x]==k){
		height[x]=-1;
		ans[++cnt]=x;
	}
}

int main()
{
	// freopen("1.in", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T; cin >> T;
	while(T--) {
		cnt=0;
		cin >> n >> m;
		for(int i = 1; i <= n; i++) {
			e[i].clear();
			par[i] = i;
		}
		for(int i = 1; i <= m; i++) {
			int x, y;
			cin >> x >> y;
			if(Find(x) == Find(y)) continue;
			par[Find(x)] = Find(y);
			e[x].push_back(y); e[y].push_back(x);
		}
		k = sqrt(n);
		if(k*k < n) k++;
		dfs(1, 0);

		//vector<int> ans;
		/*for(int i = 1; i <= n; i++) {
			// if(dep[i]%(k+1) == 1) ans.push_back(i);
			if(height[i]%(k+1) == 0) ans.push_back(i);
		}
		if((int)ans.size() < k) {
			if(ans.size() == 0 || (ans[0] != 1))
				ans.push_back(1);
		}*/
		if(cnt < k && ans[cnt] != 1) ans[++cnt]=1;
		cout << cnt << endl;
		for(int i=1;i<=cnt;i++) printf("%d ", ans[i]);
		puts("");
	}
	return 0;
}

詳細信息

Test #1:

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

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:

2
1
2 1 
1 

result:

ok correct (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 25ms
memory: 10832kb

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
1
2
1
1
3
1
2
3
1
4
2
2
2
1
3
1
1
2
1
2
2
2
2
1
3
1
2
1
1
4
2
2
3
1
2
2
2
3
1
3
1
2
2
1
2
2
2
2
1
3
1
2
2
1
4
2
2
1
1
2
2
2
2
1
2
1
2
2
1
3
1
2
1
1
4
1
1
2
1
4
2
2
2
1
3
2
2
2
1
3
2
2
2
1
4
2
2
2
1
1
2
2
2
1
1
2
1
2
1
1
2
2
2
1
3
2
2
2
1
2
1
1
2
1
3
2
3
3
1
1
2
2
2
1
3
2
2
3
1
3
2
2
2
1
3
2
2
1
1
...

result:

wrong answer Condition failed: "subset.size() == sz" (test case 1)