QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#265875#2341. Dead-End DetectorInfinityNS#WA 325ms93512kbC++143.5kb2023-11-25 22:01:092023-11-25 22:01:09

Judging History

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

  • [2023-11-25 22:01:09]
  • 评测
  • 测评结果:WA
  • 用时:325ms
  • 内存:93512kb
  • [2023-11-25 22:01:09]
  • 提交

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