QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#127548	#6634. Central Subset	shielder	WA	23ms	8232kb	C++20	1.7kb	2023-07-19 19:35:37	2023-07-19 19:35:40

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-19 19:35:40]
评测

测评结果：WA
用时：23ms
内存：8232kb

查看

[2023-07-19 19:35:37]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> e[N];
vector<int> ans;
int dis[N];
int n, m, k;
int x ,y;
bool vis[N];
bool bfs(int x){
     for(int i = 1;i <= n;i++) vis[i] = 0;
     queue<int> q;
     q.push(x);
     ans.clear();
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto y : e[u]){
            if(vis[y]) continue;
            vis[y] = 1;
            dis[y] = dis[u] + 1;
            q.push(y);
        }
    }
    for(int i = 1;i <= n;i++){
        if(dis[i]%(k) == 0){
            ans.push_back(i);
        }
    }
    if(ans.size() == 0) ans.push_back(1);
    if(ans.size()  <= k)
    return 1;
    return 0;
}
int main(){
    int tt;
    cin >> tt;
    while(tt--){
        cin >> n >>m;
        ans.clear();
        for(int i = 1;i <= n;i++){
                e[i].clear();
            vis[i] = 0;
            dis[i] = 0;
        }
        k = ceil(sqrt(n));
        for(int i = 1;i <= m;i++){
            cin >> x >> y;
            e[x].push_back(y);
            e[y].push_back(x);
        }
        for(int i = 1; i<= n;i++){
         bool f = bfs(i);
         if(f){
        cout << ans.size() << "\n";
        for(auto x : ans){
            cout << x << " ";
        }
        cout << "\n";
        }
        break;
        }
    }
    return 0;
}
/*
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
*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 8232kb

input:

output:

result:

ok correct (2 test cases)

Test #2:

score: -100

Wrong Answer

time: 23ms

memory: 8136kb

input:

output:

3
5 9 13 
2
5 6 
2
5 9 
1
1 
1
1 
2
4 7 
1
1 
2
5 11 
3
5 6 15 
1
1 
3
6 11 16 
2
4 5 
2
5 9 
2
9 10 
1
1 
3
5 9 13 
3
5 6 7 
1
1 
1
1 
2
1 3 
2
4 7 
2
5 11 
2
11 12 
1
1 
3
5 9 13 
2
4 6 
4
5 9 12 16 
2
1 3 
1
1 
4
6 11 16 21 
4
6 7 10 12 
2
5 11 
4
7 8 9 16 
1
1 
1
4 
2
4 5 
2
5 10 
5
6 7 8 20 21 ...

result:

wrong answer Condition failed: "getMaxBfsDist(n, subset) <= csqrtn" (test case 19)