Submission #397188

#	Time	Username	Problem	Language	Result	Execution time	Memory
397188		Nima_Naderi	Pipes (CEOI15_pipes)	C++14	50 / 100	1498 ms	38896 KiB

pipes

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e5 + 1;
int n, m;
int Par[2][MXN], Sz[2][MXN], M[MXN], H[MXN];
vector<int> adj[MXN];
int Find(const bool &f, const int &x){
    return (Par[f][x] == x ? x : Par[f][x] = Find(f, Par[f][x]));
}
bool Union(const bool &f, int x, int y){
    x = Find(f, x), y = Find(f, y);
    if(x == y) return 0;
    if(Sz[f][x] < Sz[f][y]) swap(x, y);
    Sz[f][x] += Sz[f][y], Par[f][y] = x;
    return 1;
}
void add_edge(const int &u, const int &v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}
void dfs(const int &u, const int &par){
    M[u] = H[u]; int c = 0;
    for(auto v : adj[u]){ c += (v == par);
        if(v == par) continue;
        if(H[v]) M[u] = min(M[u], H[v]);
        else{
            H[v] = H[u] + 1;
            dfs(v, u);
            M[u] = min(M[u], M[v]);
        }
    }
    if(c == 1 && M[u] == H[u]){
        cout << u << ' ' << par << '\n';
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m;
    iota(Par[0], Par[0] + n + 1, 0), fill(Sz[0], Sz[0] + n + 1, 1);
    iota(Par[1], Par[1] + n + 1, 0), fill(Sz[0], Sz[0] + n + 1, 1);
    for(int i = 1; i <= m; i ++){
        int u, v; cin >> u >> v;
        if(Union(0, u, v)){
            add_edge(u, v);
            continue;
        }
        if(Union(1, u, v)){
            add_edge(u, v);
            continue;
        }
    }
    for(int i = 1; i <= n; i ++){
        if(!H[i]) H[i] = 1, dfs(i, 0);
    }
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10