QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127452#6634. Central SubsetshielderWA 31ms29548kbC++202.4kb2023-07-19 18:11:032023-07-19 18:11:04

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 18:11:04]
  • 评测
  • 测评结果：WA
  • 用时：31ms
  • 内存：29548kb
查看
  • [2023-07-19 18:11:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
vector<int> v[N], e[N];
int a[N], b[N];
int dis[N], dep[N];
bool vis[N];
vector<int> ans;
int n, m, k;
int x, y;
int ed, mxdis, st;int _tmp;
// void bfs(int st){
//     mxdis= 0;
//     queue<int> q;
//     q.push(st);
//     dis[st] = 0;
//     vis[st] = 1;
//     while(!q.empty()){
//         int x = q.front();
//         q.pop();
//         for(auto y : v[x]){
//             if(vis[y]) continue;
//             vis[y] = 1;
//             e[x].push_back(y);
//             dis[y] = dis[x] + 1;
//             q.push(y);
//         }
//     }
// }
void _dfs(int x){
    if(vis[x]) return;
    vis[x]=1;
    for(auto y:v[x]){
        if(vis[y]) continue;
        _dfs(y);
        dis[x]=max(dis[x],dis[y]+1);
    }
    if(dis[x]>=k){ans.push_back(x);dis[x]=-1;}
}
// int dfs(int x){
//     if(e[x].size() == 0){
//         dep[x] = 0;
//         return 0 ;
//     }
//     int mx = 0;
//     for(auto y : e[x]) mx = max(dfs(y), mx);
//     ++mx;
//     dep[x]=mx;
//     if((mx == k || mx %(2*k)==0)){
//        ans.push_back(x);
//     }
//     return mx;
// }
// int dfs_1(int x){
//     if(e[x].size() == 0){
//         dep[x] = 0;
//         return 0 ;
//     }
//     int mx=0;
//     for(auto y : e[x]) mx = max(dfs_1(y), mx);
//     ++mx;
//     return mx;
// }

int main(){
    int tt;
    cin >> tt;
    while(tt--){
        cin >> n >> m;
        ans.clear();
        k = ceil(sqrt(n));
        dis[1]=-1;
        for(int i = 1;i <= m;i++){
            cin >>x >> y;
            v[x].emplace_back(y);
            v[y].emplace_back(x);
        }
        // if(n == 1){
        //     cout << "1\n1\n";
        //     continue;
        // }
        // st=1;
        // bfs(st);//cout << "-----------\n";
        // _tmp=dfs_1(st);
        // dfs(st);
        // ans.push_back(st);
        _dfs(1);
        // if(ans.size() > k) cout << "-1\n";
        // else{
            if(ans.size()==0) ans.push_back(1);
            cout <<ans.size() << "\n";
            for(auto x : ans) cout <<x << " ";
            cout << "\n";
        // }
        for(int i = 1;i <= n;i++){
            v[i].clear();
            e[i].clear();
            vis[i] = 0;
        }
   }
   return 0;
}
/*
16 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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:

1
2 
1
1

result:

ok correct (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 31ms
memory: 29360kb

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
11 6 1 
1
2 
1
2 
1
1 
1
1 
2
7 3 
1
1 
3
6 5 2 
3
10 6 2 
1
2 
4
15 11 5 1 
4
6 7 3 2 
1
2 
3
15 10 2 
3
5 3 2 
3
12 7 2 
2
3 2 
1
1 
3
6 8 2 
1
2 
2
4 3 
1
2 
2
6 2 
3
14 8 3 
3
6 4 1 
4
12 11 7 2 
2
3 1 
4
16 7 5 2 
1
3 
2
8 2 
4
16 11 6 1 
5
12 6 7 3 2 
3
7 6 2 
3
11 6 2 
2
3 2 
1
3 
2
7 3 
2
...

result:

wrong answer Integer 4 violates the range [1, 3] (test case 12)
English 繁體中文 简体中文

Server Time: 2024-12-05 10:15:06 | OpenSource Project