QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#677228#995. 桥RDFZchenyyWA 4ms6320kbC++141.0kb2024-10-26 10:39:042024-10-26 10:39:05

Judging History

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

  • [2024-10-26 10:39:05]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:6320kb
  • [2024-10-26 10:39:04]
  • 提交

answer

#include<bits/stdc++.h>

#define MAXN 100005
#define MAXM 1000005

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

int n,m;
Edge e[MAXN]; int h[MAXN],ec=0;
int x,y;
int dfn[MAXN],low[MAXN],idx;

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

void tarjan(int u){
	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{
			e[i].tag=1; e[i^1].tag=-1;
			tarjan(v);
			low[u]=std::min(low[u],low[v]);
		}
	}
	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);
	}
	tarjan(1);
	for(int i=0;i<=2*m-1;i+=2){
		if(e[i].tag){
			bool ok=true;
			if(e[i].tag>0){
				if(low[e[i].v]==dfn[e[i].v]) ok=false;
			}else{
				if(low[e[i^1].v]==dfn[e[i^1].v]) ok=false;
			}
			if(!ok){
				std::cout<<e[i^1].v<<' '<<e[i].v<<'\n';
			}
		}
	}

	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 6320kb

input:

24942 387166
12556 21443
22404 16376
11073 24296
1535 11968
23745 2818
5073 12731
22550 14761
24118 12008
22695 18979
15118 13639
2080 8721
692 22578
22581 15267
9278 4127
7457 21674
17693 23448
10949 23429
9700 6009
14140 5064
7742 15164
17336 1662
18903 9760
17645 19575
6540 11942
11 4937
15282 10...

output:

12556 21443
23086 9796
16647 15755
18001 13919
16116 23489
4177 2255
23771 3480
23853 24806
22479 23598
17360 23805
2851 20038
13838 13214
1072 24452
20090 11953
4957 1649
18703 21385
24668 18056
1999 1533
6170 15332
16977 12396
24347 18354
2286 689
13007 13992
5350 17266
9066 19664
12680 19195
5145...

result:

wrong output format Extra information in the output file