QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#677374 | #996. 割点 | RDFZchenyy | WA | 0ms | 8328kb | C++14 | 1.1kb | 2024-10-26 11:39:12 | 2024-10-26 11:39:13 |
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[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;
}
Details
Tip: Click on the bar to expand more detailed information
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'