oj.uz

Submission #1055304

# Submission time Handle Problem Language Result Execution time Memory
1055304 2024-08-12T16:47:43 Z vjudge1 Pipes (CEOI15_pipes) C++17
40 / 100
 499 ms 41552 KB 
#include <bits/stdc++.h>
using namespace std;
using vi = vector <int>;
using uc = unsigned char;

const int MAXN = 8E4;
vector <uc> adj1[MAXN];
vector <uc> adj2[MAXN];
int deg[MAXN];
bitset <MAXN> vis1, vis2;
int tin[MAXN], fup[MAXN], timer = 0;

uc f1 (int x) { return x&0xff; }
uc f2 (int x) { return x>>8&0xff; }
bool f3 (int x) { return x>>16&1; }
int frec (uc v1, uc v2, bool v3) { return int(v1)|int(v2)<<8|int(v3)<<16; }

void dfs (int u, int par) {
    vis1[u] = true;
    fup[u] = tin[u] = timer++;
    for (int i = 0; i < deg[u]; i++) {
        int v = frec(adj1[u][i<<1], adj1[u][i<<1|1], bool(adj2[u][i>>3]>>(i&7)&1));
        if (v == par) { par = u; continue; }
        if (vis2[v]) continue;
        if (vis1[v]) {
            fup[u] = min(fup[u], tin[v]);
        } else {
            dfs(v, u);
            fup[u] = min(fup[u], fup[v]);
            if (fup[v] == tin[v]) { // bridge (u, v)
                cout << u+1 << ' ' << v+1 << '\n';
            }
        }
    }
    vis2[u] = true;
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        adj1[u].push_back(f1(v));
        adj1[u].push_back(f2(v));
        if ((deg[u]&7) == 0) adj2[u].push_back(0);
        adj2[u].back() |= f3(v)<<(deg[u]&7);
        adj1[v].push_back(f1(u));
        adj1[v].push_back(f2(u));
        if ((deg[v]&7) == 0) adj2[v].push_back(0);
        adj2[v].back() |= f3(u)<<(deg[v]&7);
        deg[u]++; deg[v]++;
    }
    for (int u = 0; u < n; u++) {
        if (vis2[u]) continue;
        dfs(u, u);
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5468 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9752 KB Output is correct
2 Correct 78 ms 9044 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 12116 KB Output is correct
2 Correct 146 ms 13932 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 9820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 9564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 9560 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -