QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94734 | #2341. Dead-End Detector | DaiRuiChen007 | AC ✓ | 851ms | 98264kb | C++14 | 2.6kb | 2023-04-07 17:19:30 | 2023-04-07 17:19:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
bool cut[MAXN],vis[MAXN];
int dfn[MAXN],low[MAXN],dcnt;
int siz[MAXN],col[MAXN],cnt[MAXN],all[MAXN];
int u[MAXN],v[MAXN];
struct node {
int u,v,id;
node(int _u=0,int _v=0,int _id=0): u(_u),v(_v),id(_id) {}
};
vector <node> G[MAXN],E[MAXN],ans;
inline void tarjan(int p,int fa) {
dfn[p]=low[p]=++dcnt;
for(auto e:G[p]) {
if(e.v==fa) continue;
if(!dfn[e.v]) {
tarjan(e.v,p);
low[p]=min(low[p],low[e.v]);
if(low[e.v]>dfn[p]) cut[e.id]=true;
} else low[p]=min(low[p],dfn[e.v]);
}
}
signed main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
::u[i]=u,::v[i]=v;
G[u].push_back(node(u,v,i));
G[v].push_back(node(v,u,i));
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
int tot=0;
for(int i=1;i<=n;++i) {
if(col[i]) continue;
++tot;
auto dfs=[&](auto self,int p) -> void {
col[p]=tot,++siz[tot];
for(auto e:G[p]) if(!cut[e.id]&&!col[e.v]) self(self,e.v);
};
dfs(dfs,i);
}
for(int u=1;u<=n;++u) {
for(auto e:G[u]) {
if(!cut[e.id]) continue;
E[col[e.u]].push_back(node(col[e.u],col[e.v],e.id));
E[col[e.v]].push_back(node(col[e.v],col[e.u],e.id));
cut[e.id]=false;
}
}
for(int i=1;i<=tot;++i) {
if(vis[i]) continue;
int rt=0;
auto init=[&](auto self,int p,int fa) -> void {
cnt[p]=(siz[p]==1)?1:0,all[p]=1,vis[p]=true;
if(siz[p]>1) rt=p;
for(auto e:E[p]) {
if(e.v!=fa) {
self(self,e.v,p);
cnt[p]+=cnt[e.v];
all[p]+=all[e.v];
}
}
};
init(init,i,0);
if(rt) {
init(init,rt,0);
auto dfs=[&](auto self,int p,int fa) -> void {
for(auto e:E[p]) {
if(e.v==fa) continue;
if(cnt[e.v]==all[e.v]) {
int x=e.id;
if(col[u[x]]==p) ans.push_back(node(u[x],v[x],0));
else ans.push_back(node(v[x],u[x],0));
} else self(self,e.v,p);
}
};
dfs(dfs,rt,0);
} else {
auto dfs=[&](auto self,int p,int fa) -> void {
for(auto e:E[p]) {
if(e.v==fa) continue;
if(E[p].size()==1) {
int x=e.id;
if(col[u[x]]==p) ans.push_back(node(u[x],v[x],0));
else ans.push_back(node(v[x],u[x],0));
}
if(E[e.v].size()==1) {
int x=e.id;
if(col[u[x]]==p) ans.push_back(node(v[x],u[x],0));
else ans.push_back(node(u[x],v[x],0));
}
self(self,e.v,p);
}
};
dfs(dfs,i,0);
}
}
printf("%d\n",(int)ans.size());
sort(ans.begin(),ans.end(),[&](node A,node B) {
if(A.u==B.u) return A.v<B.v;
return A.u<B.u;
});
for(auto e:ans) printf("%d %d\n",e.u,e.v);
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 5ms
memory: 34864kb
Test #2:
score: 0
Accepted
time: 3ms
memory: 36600kb
Test #3:
score: 0
Accepted
time: 372ms
memory: 74672kb
Test #4:
score: 0
Accepted
time: 2ms
memory: 33892kb
Test #5:
score: 0
Accepted
time: 3ms
memory: 34764kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 37432kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 36392kb
Test #8:
score: 0
Accepted
time: 18ms
memory: 41024kb
Test #9:
score: 0
Accepted
time: 4ms
memory: 35620kb
Test #10:
score: 0
Accepted
time: 6ms
memory: 36260kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 36952kb
Test #12:
score: 0
Accepted
time: 1ms
memory: 34756kb
Test #13:
score: 0
Accepted
time: 100ms
memory: 47944kb
Test #14:
score: 0
Accepted
time: 108ms
memory: 48168kb
Test #15:
score: 0
Accepted
time: 834ms
memory: 95556kb
Test #16:
score: 0
Accepted
time: 443ms
memory: 92600kb
Test #17:
score: 0
Accepted
time: 494ms
memory: 97304kb
Test #18:
score: 0
Accepted
time: 463ms
memory: 96468kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 36232kb
Test #20:
score: 0
Accepted
time: 1ms
memory: 36432kb
Test #21:
score: 0
Accepted
time: 10ms
memory: 35096kb
Test #22:
score: 0
Accepted
time: 140ms
memory: 46684kb
Test #23:
score: 0
Accepted
time: 851ms
memory: 93284kb
Test #24:
score: 0
Accepted
time: 179ms
memory: 98264kb
Test #25:
score: 0
Accepted
time: 797ms
memory: 97116kb
Test #26:
score: 0
Accepted
time: 168ms
memory: 74416kb
Test #27:
score: 0
Accepted
time: 478ms
memory: 76104kb
Test #28:
score: 0
Accepted
time: 465ms
memory: 75620kb
Test #29:
score: 0
Accepted
time: 443ms
memory: 74312kb
Test #30:
score: 0
Accepted
time: 177ms
memory: 80280kb
Test #31:
score: 0
Accepted
time: 392ms
memory: 81388kb
Test #32:
score: 0
Accepted
time: 213ms
memory: 95508kb
Test #33:
score: 0
Accepted
time: 397ms
memory: 95288kb
Test #34:
score: 0
Accepted
time: 799ms
memory: 93280kb
Test #35:
score: 0
Accepted
time: 734ms
memory: 88532kb
Test #36:
score: 0
Accepted
time: 807ms
memory: 91136kb
Test #37:
score: 0
Accepted
time: 821ms
memory: 94020kb
Test #38:
score: 0
Accepted
time: 754ms
memory: 88532kb
Test #39:
score: 0
Accepted
time: 649ms
memory: 84024kb
Test #40:
score: 0
Accepted
time: 537ms
memory: 74800kb
Test #41:
score: 0
Accepted
time: 699ms
memory: 86232kb
Test #42:
score: 0
Accepted
time: 551ms
memory: 73840kb
Test #43:
score: 0
Accepted
time: 594ms
memory: 72352kb
Test #44:
score: 0
Accepted
time: 469ms
memory: 95196kb
Test #45:
score: 0
Accepted
time: 380ms
memory: 95304kb