oj.uz

Submission #1055284

# Submission time Handle Problem Language Result Execution time Memory
1055284 2024-08-12T16:28:18 Z vjudge1 Pipes (CEOI15_pipes) C++17
0 / 100
 1075 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
using vi = vector <int>;
using uc = unsigned char;

const int MAXN = 1E5+16;
vector <uc> adj1[MAXN];
vector <bool> adj2[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 < adj1[u].size(); i += 2) {
        int v = frec(adj1[u][i], adj1[u][i+1], adj2[u][i>>1]);
        if (v == par) 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));
        adj2[u].push_back(f3(v));
        adj1[v].push_back(f1(u));
        adj1[v].push_back(f2(u));
        adj2[v].push_back(f3(u));
    }
    for (int u = 0; u < n; u++) {
        if (vis2[u]) continue;
        dfs(u, u);
    }
    return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<unsigned char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < adj1[u].size(); i += 2) {
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Incorrect 1 ms 7260 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Incorrect 3 ms 7772 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1075 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -