oj.uz

답안 #1055298

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1055298 2024-08-12T16:35:48 Z vjudge1 Pipes (CEOI15_pipes) C++17
30 / 100
 502 ms 53328 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 <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) { 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));
        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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6608 KB Output is correct
2 Correct 3 ms 6236 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 10456 KB Output is correct
2 Correct 69 ms 15392 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 13140 KB Output is correct
2 Runtime error 160 ms 25988 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 211 ms 20564 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 297 ms 29572 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 502 ms 53328 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 11608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 11616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 11612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -