QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#677288 | #995. 桥 | RDFZchenyy | WA | 6ms | 6960kb | C++14 | 1.1kb | 2024-10-26 10:58:39 | 2024-10-26 10:58:40 |
Judging History
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);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
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^1].v]) ok=false;
}else{
if(low[e[i^1].v]>dfn[e[i].v]) ok=false;
}
if(!ok){
std::cout<<e[i^1].v<<' '<<e[i].v<<'\n';
}
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 6960kb
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