oj.uz

Submission #1026990

# Submission time Handle Problem Language Result Execution time Memory
1026990 2024-07-18T16:55:54 Z vjudge1 Pipes (CEOI15_pipes) C++17
0 / 100
 695 ms 13144 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 if(mst2.join_set(u,v)){
			graph[u].push_back(v);
			graph[v].push_back(u);
		}
    }
    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 3 ms 3420 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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