oj.uz

Submission #232000

# Submission time Handle Problem Language Result Execution time Memory
232000 2020-05-15T16:11:18 Z DodgeBallMan Pipes (CEOI15_pipes) C++14
60 / 100
 1478 ms 30204 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 116 ms 8604 KB Output is correct
2 Correct 113 ms 8312 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 13432 KB Output is correct
2 Correct 235 ms 14712 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 342 ms 21496 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 10872 KB Output is correct
2 Correct 450 ms 8440 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 748 ms 23416 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1002 ms 30204 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1295 ms 14428 KB Output is correct
2 Runtime error 1156 ms 20844 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1478 ms 14584 KB Output is correct
2 Correct 1404 ms 12140 KB Output is correct