oj.uz

Submission #1115941

# Submission time Handle Problem Language Result Execution time Memory
1115941 2024-11-21T05:53:13 Z vjudge1 Pipes (CEOI15_pipes) C++17
0 / 100
 678 ms 65536 KB 
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(1E5) + 5;
constexpr int max_M = int(6E6) + 5;

int N, M;
std::vector<int> adj[max_N], ans;
int tin[max_N], low[max_N], timer;
int A[max_M], B[max_M];

void tarjan(int v, int pr) {
    tin[v] = low[v] = ++timer;
    for (auto i : adj[v]) {
        if (i == pr) {
            continue;
        }
        int u = A[i] ^ B[i] ^ v;
        if (tin[u] == 0) {
            tarjan(u, i);
            low[v] = std::min(low[v], low[u]);
        } else {
            low[v] = std::min(low[v], tin[u]);
        }
    }
    if (pr != -1 && low[v] == tin[v]) {
        ans.emplace_back(pr);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
        adj[A[i]].emplace_back(i);
        adj[B[i]].emplace_back(i);
    }

    for (int i = 0; i < N; ++i) {
        if (tin[i] == 0) {
            tarjan(i, -1);
        }
    }

    std::cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); ++i) {
        std::cout << A[ans[i]] + 1 << ' ' << B[ans[i]] + 1 << '\n';
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5200 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5712 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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