oj.uz

Submission #397195

# Submission time Handle Problem Language Result Execution time Memory
397195 2021-05-01T17:11:55 Z Nima_Naderi Pipes (CEOI15_pipes) C++14
100 / 100
 1507 ms 13604 KB 
///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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3960 KB Output is correct
2 Correct 7 ms 3660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 4112 KB Output is correct
2 Correct 117 ms 3964 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 4656 KB Output is correct
2 Correct 236 ms 4256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 6100 KB Output is correct
2 Correct 311 ms 6176 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 10644 KB Output is correct
2 Correct 427 ms 7248 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 11668 KB Output is correct
2 Correct 745 ms 9380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 13604 KB Output is correct
2 Correct 900 ms 9140 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1155 ms 13580 KB Output is correct
2 Correct 1117 ms 9172 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 12852 KB Output is correct
2 Correct 1507 ms 9844 KB Output is correct