oj.uz

Submission #397189

# Submission time Handle Problem Language Result Execution time Memory
397189 2021-05-01T17:08:05 Z Nima_Naderi Pipes (CEOI15_pipes) C++14
70 / 100
 1512 ms 32396 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], 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;
    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);
    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)){
            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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3148 KB Output is correct
2 Correct 6 ms 2840 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2980 KB Output is correct
2 Correct 116 ms 2888 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 3640 KB Output is correct
2 Correct 240 ms 3244 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 5304 KB Output is correct
2 Runtime error 320 ms 18852 KB Memory limit exceeded

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 10580 KB Output is correct
2 Correct 412 ms 7052 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 11788 KB Output is correct
2 Correct 784 ms 10592 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 13964 KB Output is correct
2 Correct 911 ms 11848 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1189 ms 13968 KB Output is correct
2 Runtime error 1162 ms 19340 KB Memory limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 13336 KB Output is correct
2 Runtime error 1512 ms 32396 KB Memory limit exceeded