oj.uz

Submission #232116

# Submission time Handle Problem Language Result Execution time Memory
232116 2020-05-16T05:36:55 Z DodgeBallMan Pipes (CEOI15_pipes) C++14
100 / 100
 1385 ms 15040 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define eb emplace_back
#define em emplace
 
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
const int MAX = 101010;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
 
struct UFT {
    vector <int> p;
    UFT(int n) {
        p.resize(n+1);
        for(int i = 1; i <= n; i++) p[i] = i;
    }
 
    int find(int x) {
        return p[x] == x ? p[x] : p[x] = find(p[x]);
    }
    void uni(int x, int y) {
        x = find(x), y = find(y);
        p[max(x, y)] = min(x, y);
    }
};
 
vector <int> g[MAX];
int low[MAX], ord[MAX], cnt = 0;
 
void dfs(int x, int pa) {
    ord[x] = low[x] = ++cnt;
    bool was = false;
    for(auto i : g[x]) {
        if(i == pa && !was) {
            was = true;
            continue;
        }
        if(ord[i] == 0) {
            dfs(i, x);
            low[x] = min(low[x], low[i]);
        }
        else if(ord[i] < ord[x]) {
            low[x] = min(low[x], ord[i]);
        }
    }
    for(auto i : g[x]) {
        if(i == pa) continue;
        if(low[i] > ord[x]) cout << x << ' ' << i << '\n';
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m;
    cin >> n >> m;
    UFT t1(n), t2(n);
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        if(t1.find(u) != t1.find(v)) {
            t1.uni(u, v);
            g[u].eb(v), g[v].eb(u);
        }
        else if(t2.find(u) != t2.find(v)) {
            t2.uni(u, v);
            g[u].eb(v), g[v].eb(u);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(ord[i] == 0) dfs(i, 0);
    }
}

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 109 ms 3192 KB Output is correct
2 Correct 112 ms 2924 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 3960 KB Output is correct
2 Correct 210 ms 3320 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 5624 KB Output is correct
2 Correct 283 ms 5244 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 11384 KB Output is correct
2 Correct 393 ms 7288 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 12664 KB Output is correct
2 Correct 702 ms 9592 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 15040 KB Output is correct
2 Correct 892 ms 9440 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1159 ms 14980 KB Output is correct
2 Correct 1088 ms 9312 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 14464 KB Output is correct
2 Correct 1334 ms 11192 KB Output is correct