oj.uz

Submission #753222

# Submission time Handle Problem Language Result Execution time Memory
753222 2023-06-04T20:35:25 Z Ronin13 Pipes (CEOI15_pipes) C++14
100 / 100
 1022 ms 12272 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 =  100001;
vector <int> par(nmax);
bool marked[nmax];
int p[nmax][2];
int sz[nmax];
pii edge[nmax];

void make_set(int v){
    p[v][0] = p[v][1] = v;
    sz[v] = 1;
    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] < sz[B])
        swap(a,b), swap(A, B), sz[A] += sz[B];
    union_sets(A, B, 0);
    int last = find_set(b, 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--){
        par[path[i]] = path[i - 1];
        edge[path[i]] = edge[path[i - 1]];
    }
    par[path[0]] = find_set(a ,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);
    x = find_set(x, 1);
    vector <int> path_a, path_b;
    while(a != x || b !=x){
        path_a.pb(a);
        if(marked[a] && a != x){
            lca = a;
            break;
        }
        marked[a] = true;
        path_b.pb(b);
        if(a != par[a])
        a = find_set(par[a], 1);
        if(marked[b] && b != x){
            lca = b;
            break;
        }
        marked[b] = true;
        if(b != par[b])
        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);
    }
    int u, v;
    for(int i= 1; i <= m; ++i){
        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:55:13: warning: unused variable 'b1' [-Wunused-variable]
   55 |         int b1 = x;
      |             ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 5 ms 992 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 1000 KB Output is correct
2 Correct 87 ms 980 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 1260 KB Output is correct
2 Correct 155 ms 1256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 2004 KB Output is correct
2 Correct 227 ms 2732 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 3916 KB Output is correct
2 Correct 407 ms 3876 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 4444 KB Output is correct
2 Correct 515 ms 4196 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 5612 KB Output is correct
2 Correct 622 ms 5196 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 5560 KB Output is correct
2 Correct 807 ms 5248 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 6696 KB Output is correct
2 Correct 1018 ms 12272 KB Output is correct