QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135098 | #6634. Central Subset | Team_name# | WA | 25ms | 10832kb | C++20 | 1.4kb | 2023-08-05 11:29:22 | 2023-08-05 11:29:24 |
Judging History
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)