QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#677374#996. 割点RDFZchenyyWA 0ms8328kbC++141.1kb2024-10-26 11:39:122024-10-26 11:39:13

Judging History

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

  • [2024-10-26 11:39:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:8328kb
  • [2024-10-26 11:39:12]
  • 提交

answer

#include<bits/stdc++.h>

#define MAXN 100005
#define MAXM 1000005

struct Edge{
	int v,nxt;
	int tag;
};

int n,m;
Edge e[MAXM]; int h[MAXN],ec=0;
int x,y;
int dfn[MAXN],low[MAXN],idx;
int fa[MAXN],sz[MAXN];
int cnt=0;
std::vector<int> ans;

void adde(int u,int v){
	e[ec].nxt=h[u]; e[ec].v=v;
	h[u]=ec; ec++;
	return;
}

void tarjan(int u){
	int ok=1;
	low[u]=dfn[u]=++idx;
	for(int i=h[u];i+1;i=e[i].nxt){
		int v=e[i].v;
		if(e[i].tag) continue;
		if(dfn[v]){
			low[u]=std::min(low[u],dfn[v]);
		}else{
			sz[u]++,fa[v]=u;
			e[i].tag=1; e[i^1].tag=-1;
			tarjan(v);
			low[u]=std::min(low[u],low[v]);
			if(low[v]>=dfn[u]) ok=0;
		}
	}
	if(!fa[u]){
		if(sz[u]>1) ans.emplace_back(u);
	}else if(!ok){
		ans.emplace_back(u);
	}
	return;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0),std::cout.tie(0);

	std::cin>>n>>m;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=m;i++){
		std::cin>>x>>y;
		adde(x,y),adde(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	std::cout<<ans.size()<<'\n'; for(int i:ans) std::cout<<i<<'\n';

	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 8328kb

input:

12783 21968
4933 7832
8238 2739
3628 7841
9169 6390
7850 8797
8120 8710
5306 9807
10166 2063
2666 5157
5015 4651
4790 12586
10366 7137
12440 7218
6330 3670
2735 8492
1968 2750
6237 1112
6578 9221
743 3820
7155 4583
2537 9747
11331 9916
4454 5631
2978 10340
5293 1803
4944 4296
11800 2742
7903 2018
10...

output:

1440
12646
6328
4803
858
12304
7163
7840
626
11358
12479
4945
8641
5987
11591
4703
9966
4334
5848
12452
691
10651
6915
8610
358
6974
7069
8823
8689
9163
155
12164
4975
9863
8347
7120
6622
930
3622
9319
8542
5146
5285
8838
6333
3644
8592
6158
9496
4604
27
2677
11730
9054
3911
5903
3069
12081
5583
435...

result:

wrong answer 2nd numbers differ - expected: '13', found: '12646'