oj.uz

Submission #397188

# Submission time Handle Problem Language Result Execution time Memory
397188 2021-05-01T17:06:57 Z Nima_Naderi Pipes (CEOI15_pipes) C++14
50 / 100
 1498 ms 38896 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], 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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 8496 KB Output is correct
2 Correct 134 ms 8224 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 13380 KB Output is correct
2 Correct 260 ms 14584 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 364 ms 21648 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 15232 KB Output is correct
2 Correct 449 ms 9028 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 727 ms 16804 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 972 ms 22676 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1160 ms 26632 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1498 ms 38896 KB Memory limit exceeded
2 Halted 0 ms 0 KB -