Submission #397195

#	Time	Username	Problem	Language	Result	Execution time	Memory
397195		Nima_Naderi	Pipes (CEOI15_pipes)	C++14	100 / 100	1507 ms	13604 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];
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;
    Par[f][y] = x;
    return 1;
}
void dfs(const int &u, const int &par){
    Par[1][u] = Par[0][u]; int c = 0;
    for(auto v : adj[u]){ c += (v == par);
        if(v == par) continue;
        if(Par[0][v]) Par[1][u] = min(Par[1][u], Par[0][v]);
        else{
            Par[0][v] = Par[0][u] + 1;
            dfs(v, u);
            Par[1][u] = min(Par[1][u], Par[1][v]);
        }
    }
    if(c == 1 && Par[1][u] == Par[0][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);
    iota(Par[1], Par[1] + n + 1, 0);
    for(int i = 1; i <= m; i ++){
        int u, v; cin >> u >> v;
        if(Union(0, u, v)){
            adj[u].push_back(v);
            adj[v].push_back(u);
            continue;
        }
        if(Union(1, u, v)){
            adj[u].push_back(v);
            adj[v].push_back(u);
            continue;
        }
    }
    memset(Par, 0, sizeof Par);
    for(int i = 1; i <= n; i ++){
        if(!Par[0][i]) Par[0][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: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10