oj.uz

Submission #753215

# Submission time Handle Problem Language Result Execution time Memory
753215 2023-06-04T20:18:12 Z Ronin13 Pipes (CEOI15_pipes) C++14
0 / 100
 148 ms 65536 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#define pii pair<int,int>
using namespace std;

const int nmax =  20001;
vector <int> par(nmax);
bool marked[nmax];
int p[nmax][2];
int sz[nmax][2];
pii edge[nmax];

void make_set(int v){
    p[v][0] = p[v][1] = v;
    sz[v][0] = sz[v][1] = v;
    par[v] = v;
}

int find_set(int v, int ind){
    return p[v][ind] == v ? v : p[v][ind] = find_set(p[v][ind], ind);
}

void union_sets(int a, int b, int ind){
    a = find_set(a, ind);
    b = find_set(b, ind);
    if(a == b)
        return;
    p[b][ind] = a;
    sz[a][ind] += sz[b][ind];
}

set <pii> bridges;

void union_trees(int a, int b){
    int A = find_set(a, 0);
    int B = find_set(b, 0);
    int a1 = a, b1 = b;
    if(A == B)
        return;
    bridges.insert({a, b});
    if(sz[A][0] < sz[B][0])
        swap(a,b), swap(A, B);
    union_sets(A, B, 0);
    int last = find_set(b, 1);
    par[last] = find_set(a, 1);
    vector <int> path;
    path.pb(last);
    while(last != find_set(B, 1)){
        int x = par[find_set(last, 1)];
        int b1 = x;
        b = find_set(x, 1);
        par[b] = last;
        swap(last, b);
        path.pb(last);
    }
    for(int i = path.size() - 1; i > 0; i--){
        edge[path[i]] = edge[path[i - 1]];
    }
    edge[path[0]] = {a1, b1};
}

void compress(int a, int b){
    int x = find_set(a, 0);
    a = find_set(a, 1);
    b = find_set(b, 1);
    int lca = find_set(x, 1);
    vector <int> path_a, path_b;
    while(a != x || b !=x){
        path_a.pb(a);
        if(marked[a]){
            lca = a;
            break;
        }
        marked[a] = true;
        path_b.pb(b);
        a = find_set(par[a], 1);
        if(marked[b]){
            lca = b;
            break;
        }
        marked[b] = true;
        b = find_set(par[b], 1);
    }
    for(int to : path_a){
        if(to == lca) break;
        bridges.erase(edge[to]);
        union_sets(lca, to, 1);
    }
    for(int to : path_b){
        if(to == lca) break;
        bridges.erase(edge[to]);
        union_sets(lca, to, 1);
    }
    for(int to : path_a)
        marked[to] = false;
    for(int to : path_b)
        marked[to] = false;
}

void add_edge(int a, int b){
    if(find_set(a, 0) != find_set(b, 0)){
        union_trees(a, b);
    }
    else{
        if(find_set(a, 1) == find_set(b, 1))
            return;
        compress(a, b);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++){
        make_set(i);
    }
    for(int i= 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        add_edge(u, v);
    }
    for(auto to : bridges)
        cout << to.f << ' ' << to.s << "\n";
}

Compilation message

pipes.cpp: In function 'void union_trees(int, int)':
pipes.cpp:56:13: warning: unused variable 'b1' [-Wunused-variable]
   56 |         int b1 = x;
      |             ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 142 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -