QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127104#6634. Central Subsetdoyo#TL 2ms11632kbC++141.4kb2023-07-19 12:59:262023-07-19 12:59:28

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 12:59:28]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:11632kb
  • [2023-07-19 12:59:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;

struct Edge
{
    int next;int to;
}edge[maxn];
int dep[maxn],n,sqn,head[maxn],cnt,m;
bool sel[maxn],vis[maxn];
void addedge(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
int dfs(int u,int fat)
{
    //返回值为所能访问到的节点的最大深度
    vis[u]=true;
    dep[u]=dep[fat]+1;
    int maxdep=dep[u];
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fat||vis[v]) continue;
        int tmp=dfs(v,u);
        maxdep=max(maxdep,tmp);
    }
    //printf("dep[%d]=%d,maxdep=%d\n",u,dep[u],maxdep);
    if(maxdep-dep[u]==sqn)
    {
        sel[u]=true;
        return 0;
    }
    else return maxdep;
}
vector<int> ans;
void work()
{
    cin>>n>>m;
    if(n/sqrt(n)==sqrt(n)) sqn=sqrt(n);
    else sqn=(int)sqrt(n)+1;
    //printf("sqn=%d\n",sqn);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
    }
    dep[0]=0;
    dfs(1,0);
    for(int i=1;i<=n;i++)
        if(sel[i]) ans.push_back(i),sel[i]=false;

    cout<<ans.size()<<endl;
    for(auto item:ans)
        cout<<item<<' ';
    for(int i=1;i<=n;i++) vis[i]=false;
}
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(0);
	int t=1;
	cin>>t;
	while(t--)
		work();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11632kb

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 2
2 1 

result:

ok correct (2 test cases)

Test #2:

score: -100
Time Limit Exceeded

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

result: