Submission #995515

#	Time	Username	Problem	Language	Result	Execution time	Memory
995515		mnbvcxz123	Pipes (CEOI15_pipes)	C++17	0 / 100	743 ms	65536 KiB

pipes

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

constexpr int N=1e5+5;

struct DSU{
    int n;
    int par[N];
    DSU(){
        n=N-1;
        iota(par,par+n+1,0);
    }
    int find_set(int x){
        if(par[x]==x)return x;
        return par[x]=find_set(par[x]);
    }
    bool same_set(int u, int v){
        return find_set(u)==find_set(v);
    }
    bool join_set(int a, int b){
        a=find_set(a);
        b=find_set(b);
        if(a==b)return 0;
        par[b]=a;
        return 1;
    }
};

DSU mst1,mst2;

vector<int>graph[N];
int last[N];
int dfs_cnt=0;
int edge_cnt=0;

void dfs(int u, int p){
    #define num mst1.par
    #define low mst2.par
    num[u]=low[u]=++dfs_cnt;
    for(const int&v:graph[u]){
        if(v==p)continue;
        if(num[v])low[u]=min(low[u],num[v]);
        else{
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=num[u])
                cout<<min(u,v)<<' '<<max(u,v)<<'\n';
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        if(mst1.join_set(u,v)){
            ++edge_cnt;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }else mst2.join_set(u,v);
    }
    for(int i=1;i<=n;++i)
        last[mst2.find_set(i)]=i;
    for(int i=1;i<=n;++i){
        int u=last[mst2.find_set(i)],v=i;
        if(u!=v){
            graph[u].push_back(v);
            graph[v].push_back(u);
        }else
            last[mst2.find_set(i)]=i;
    }
    for(int i=1;i<=n;++i)
        mst1.par[i]=mst2.par[i]=0;
    for(int i=1;i<=n;++i)
        if(!num[i])dfs(i,-1);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10