oj.uz

Submission #230372

# Submission time Handle Problem Language Result Execution time Memory
230372 2020-05-09T20:36:41 Z parsa_mobed Pipes (CEOI15_pipes) C++14
100 / 100
 1452 ms 14968 KB 
#include <bits/stdc++.h>

using namespace std;
#define adj(v, p) (v^E[p][0]^E[p][1])
const int N = 1e5 + 2;
int h[N], par[N], _par[N], E[2*N][2], id = 0;
bool mark[N];
vector <int> g[N];


void add(int u, int v) {
    E[++id][0] = u, E[id][1] = v;
    g[u].push_back(id), g[v].push_back(id);
    return ;
}
int getpar(int u) {return par[u] = (par[u] == u ? u : getpar(par[u]));}
int get_par(int u) {return _par[u] = (_par[u] == u ? u : get_par(_par[u]));}
void Union(int u, int v) {
    int ru = getpar(u), rv = getpar(v);
    if (ru == rv) {
        ru = get_par(u), rv = get_par(v);
        if (ru == rv) return ;
        _par[ru] = rv, add(u, v);
        return ;
    }
    par[ru] = rv, add(u, v);
    return ;
}
int dfs(int v, int p = 0) {
    mark[v] = 1;
    int mx = h[v];
    for (int i : g[v]) {
        if (!mark[adj(v, i)]) h[adj(v, i)] = h[v] + 1, mx = min(mx, dfs(adj(v, i), i));
        else if (i != p) mx = min(mx, h[adj(v, i)]);
    }
    if (p && mx == h[v]) cout << v << " " << adj(v, p) << "\n";
    return mx;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) par[i] = _par[i] = i;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        Union(u, v);
    }
    for (int i = 1; i <= n; i++) if (!mark[i]) dfs(i);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3328 KB Output is correct
2 Correct 9 ms 3072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 4472 KB Output is correct
2 Correct 108 ms 4216 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 4600 KB Output is correct
2 Correct 211 ms 4216 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 6136 KB Output is correct
2 Correct 282 ms 5752 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 11128 KB Output is correct
2 Correct 417 ms 8696 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 12792 KB Output is correct
2 Correct 730 ms 10236 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 14968 KB Output is correct
2 Correct 929 ms 11512 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1214 ms 14220 KB Output is correct
2 Correct 1169 ms 11640 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1452 ms 14320 KB Output is correct
2 Correct 1385 ms 10720 KB Output is correct