Submission #1115955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115955		vjudge1	Pipes (CEOI15_pipes)	C++17	10 / 100	90 ms	17992 KiB

pipes

#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 (stderr)

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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10