oj.uz

Submission #753221

# Submission time Handle Problem Language Result Execution time Memory
753221 2023-06-04T20:33:36 Z Ronin13 Pipes (CEOI15_pipes) C++14
50 / 100
 1027 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 =  100001;
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] = 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][0] < sz[B][0])
        swap(a,b), swap(A, 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 4 ms 852 KB Output is correct
2 Correct 5 ms 852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 852 KB Output is correct
2 Correct 85 ms 852 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 1108 KB Output is correct
2 Correct 193 ms 1108 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 1876 KB Output is correct
2 Correct 272 ms 16036 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 4220 KB Output is correct
2 Runtime error 411 ms 22248 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 4620 KB Output is correct
2 Runtime error 547 ms 37880 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 5604 KB Output is correct
2 Runtime error 694 ms 47044 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 5560 KB Output is correct
2 Runtime error 824 ms 58628 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1027 ms 14248 KB Output is correct
2 Runtime error 987 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -