제출 #753218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753218		Ronin13	Pipes (CEOI15_pipes)	C++14	0 / 100	146 ms	65536 KiB

pipes

#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] = 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);
    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";
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10