oj.uz

Submission #995515

# Submission time Handle Problem Language Result Execution time Memory
995515 2024-06-09T08:33:36 Z mnbvcxz123 Pipes (CEOI15_pipes) C++17
0 / 100
 743 ms 65536 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3672 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3928 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 9300 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 13648 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 173 ms 20892 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 252 ms 27448 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 371 ms 40100 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 516 ms 51280 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 691 ms 62820 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 743 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -