oj.uz

Submission #232114

# Submission time Handle Problem Language Result Execution time Memory
232114 2020-05-16T05:34:43 Z DodgeBallMan Pipes (CEOI15_pipes) C++14
60 / 100
 1508 ms 25976 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 10 ms 3072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 8568 KB Output is correct
2 Correct 111 ms 8440 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 11640 KB Output is correct
2 Correct 220 ms 11400 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 767 ms 19576 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 Correct 1014 ms 13940 KB Output is correct
2 Runtime error 955 ms 25976 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1223 ms 15276 KB Output is correct
2 Runtime error 1145 ms 18808 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 1508 ms 15480 KB Output is correct
2 Correct 1442 ms 13072 KB Output is correct