oj.uz

Submission #1115944

# Submission time Handle Problem Language Result Execution time Memory
1115944 2024-11-21T05:55:11 Z vjudge1 Pipes (CEOI15_pipes) C++17
20 / 100
 769 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);
        }
    }

    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:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < ans.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5712 KB Output is correct
2 Correct 4 ms 5456 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 682 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 698 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 769 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 659 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -