QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134878#6634. Central SubsetSolitaryDream#WA 12ms9656kbC++20975b2023-08-05 09:38:562023-08-05 09:38:58

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 09:38:58]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:9656kb
  • [2023-08-05 09:38:56]
  • 提交

answer

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

const int N=2e5+1e3+7;

int T,n,m,L;

vector<int>g[N];

int vis[N],d[N];

vector<int>ans;

void dfs(int x)
{
    d[x]=1e9;
    for(auto v:g[x])
    {
        if(vis[v])
            continue;
        vis[v]=1;
        dfs(v);
        d[x]=min(d[x],d[v]+1);
    }
    if(d[x]>L)
        ans.push_back(x),d[x]=0;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        L=0;
        while(L*L<n)
            L++;
        for(int i=1;i<=n;i++)
            vis[i]=0,g[i].clear();
        ans.clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vis[1]=1;
        dfs(1);
        printf("%d\n",(int)ans.size());
        for(int i=0;i<ans.size();i++)
            printf("%d%c",ans[i]," \n"[i+1==ans.size()]);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8584kb

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

result:

ok correct (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 12ms
memory: 9656kb

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
15 10 5
2
6 5
5
8 9 6 10 7
1
2
1
2
3
9 5 1
1
2
7
9 10 11 13 8 14 12
6
13 16 11 8 7 5
14
14 16 4 12 10 3 8 11 13 9 5 7 6 15
4
20 14 8 2
3
8 7 5
5
7 10 6 9 8
7
16 17 14 12 11 9 6
3
4 5 3
3
15 10 5
3
7 5 6
1
2
4
5 7 9 8
17
5 19 11 4 14 6 9 17 12 15 16 7 18 8 3 13 10
2
4 1
3
8 7 5
7
9 11 14 8 13 12 10...

result:

wrong answer Integer 5 violates the range [1, 4] (test case 3)