oj.uz

Submission #1115955

# Submission time Handle Problem Language Result Execution time Memory
1115955 2024-11-21T06:09:50 Z vjudge1 Pipes (CEOI15_pipes) C++17
10 / 100
 90 ms 17992 KB 
#include <bits/stdc++.h>

using i64 = long long;

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

bool start;

constexpr int max_N = int(4E3) + 5;
constexpr int max_M = int(6E5) + 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);
    }
}

bool end;

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';
    }

    std::cerr << "elapsed memory: " << (&start - &end) / 1024 / 1024 << '\n';

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13384 KB Output is correct
2 Runtime error 86 ms 17992 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 4944 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 5 ms 4944 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 4944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -