QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#265875 | #2341. Dead-End Detector | InfinityNS# | WA | 325ms | 93512kb | C++14 | 3.5kb | 2023-11-25 22:01:09 | 2023-11-25 22:01:09 |
Judging History
answer
#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
typedef pair<int,int>pii;
const int maxn=5e5+10;
vector<pii>vect[maxn];
int n,m,dsctime,disc[maxn],mind[maxn],isbridge[maxn],pos[maxn],bniz[maxn];
void go(int x,int prv){
dsctime++;
disc[x]=dsctime;
mind[x]=dsctime;
for(int i=0;i<vect[x].size();i++){
int id=vect[x][i].ff;
int eid=vect[x][i].ss;
if(id==prv)continue;
if(disc[id]==0){
go(id,x);
mind[x]=min(mind[x],mind[id]);
}
else{
if(disc[id]<disc[x])mind[x]=min(mind[x],disc[id]);
}
if(mind[id]>disc[x])isbridge[eid]=1;
}
}
void go2(int x,vector<int>&cand){
pos[x]=1;
cand.pb(x);
for(int i=0;i<vect[x].size();i++){
int id=vect[x][i].ff;
int eid=vect[x][i].ss;
if(pos[id])continue;
if(isbridge[eid])continue;
go2(id,cand);
}
}
void prek_bicbool(){
for(int i=1;i<=n;i++){
if(disc[i])continue;
go(i,0);
}
for(int i=1;i<=n;i++){
if(pos[i])continue;
vector<int>cand;
go2(i,cand);
if(cand.size()>1){
for(auto x:cand)bniz[x]=1;
}
}
//for(int i=1;i<=n;i++){
// printf("%d %d\n",i,bniz[i]);
//}
}
bool vis[maxn];
vector<int> comp;
vector<int> deg(maxn);
vector<bool> inside(maxn);
void dfs(int tr){
comp.pb(tr);
vis[tr]=1;
for(auto p:vect[tr]){
if(!vis[p.f]){
dfs(p.f);
}
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
vect[u].pb({v,i});
vect[v].pb({u,i});
}
prek_bicbool();
/*for(int i=1;i<=n;i++){
printf("%i: %i\n",i,bniz[i]);
}*/
vector<pair<int,int>> ans;
for(int i=1;i<=n;i++){
if(!vis[i]){
comp.clear();
dfs(i);
bool has=0;
for(auto p:comp){
if(bniz[p]){
has=1;
}
for(auto d:vect[p]){
deg[d.f]++;
}
}
if(!has){
for(auto p:comp){
if(deg[p]==1){
ans.pb({p,vect[p][0].f});
}
}
}
else{
queue<int> q;
for(auto p:comp){
inside[p]=1;
if(deg[p]==1){
q.push(p);
}
}
while(q.size()){
int tr=q.front();
inside[tr]=0;
q.pop();
for(auto p:vect[tr]){
if(inside[p.f]){
if(bniz[p.f]){
ans.pb({p.f,tr});
}
deg[p.f]--;
deg[tr]--;
if(deg[p.f]==1&&!bniz[p.f]){
q.push(p.f);
}
}
}
}
}
}
}
sort(ans.begin(),ans.end());
printf("%i\n",ans.size());
for(auto p:ans){
printf("%i %i\n",p.f,p.s);
}
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 6ms
memory: 20864kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 24348kb
Test #3:
score: 0
Accepted
time: 325ms
memory: 93512kb
Test #4:
score: 0
Accepted
time: 6ms
memory: 19116kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 21284kb
Test #6:
score: 0
Accepted
time: 2ms
memory: 22352kb
Test #7:
score: 0
Accepted
time: 5ms
memory: 21368kb
Test #8:
score: 0
Accepted
time: 12ms
memory: 24824kb
Test #9:
score: 0
Accepted
time: 2ms
memory: 20944kb
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 25172kb