Submission #1115996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115996		vjudge1	Pipes (CEOI15_pipes)	C++17	90 / 100	2537 ms	65536 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

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

int N, M;
std::vector<int> adj[max_N];
int cur, cedg, cnedg;
int A[S], B[S];
struct DSU {
    std::vector<int> f;
    DSU(int n) : f(n) {
        std::iota(f.begin(), f.end(), 0);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) {
            return false;
        } 
        f[a] = b;
        return true;
    }
    bool same(int a, int b) {
        return get(a) == get(b);
    }
    int operator[](int x) {
        return get(x);
    }
} belong(max_N);
std::pair<int, int> edg[3 * max_N], nedg[3 * max_N];

std::stack<int> stk;
int tin[max_N], low[max_N], comp[max_N], timer, n;
void tarjan(int v, int pr) {
    stk.emplace(v);
    tin[v] = low[v] = timer++;
    while (!adj[v].empty()) {
        int i = adj[v].back();
        adj[v].pop_back();
        if (i == pr) {
            continue;
        }
        int u = v ^ belong[nedg[i].first] ^ belong[nedg[i].second];
        if (tin[u] == -1) {
            tarjan(u, i);
            low[v] = std::min(low[v], low[u]);
        } else if (comp[u] == -1) {
            low[v] = std::min(low[v], tin[u]);
        }
    }
    if (low[v] == tin[v]) {
        int u;
        do {
            u = stk.top();
            stk.pop();
            comp[u] = n;
        } while (u != v);
        ++n;
    }
}

void recalc() {
    n = 0;
    timer = 0;
    for (int i = 0; i < N; ++i) {
        tin[i] = low[i] = comp[i] = -1;
    }

    cnedg = 0;
    for (int i = 0; i < cedg; ++i) {
        assert(cnedg < 3 * max_N);
        nedg[cnedg] = edg[i];
        adj[belong[edg[i].first]].emplace_back(cnedg);
        adj[belong[edg[i].second]].emplace_back(cnedg);
        ++cnedg;
    }
    cedg = 0;
    for (int i = 0; i < cur; ++i) {
        if (belong[A[i]] != belong[B[i]]) {
            assert(cnedg < 3 * max_N);
            nedg[cnedg] = {A[i], B[i]};
            adj[belong[A[i]]].emplace_back(cnedg);
            adj[belong[B[i]]].emplace_back(cnedg);
            ++cnedg;
        }
    }
    cur = 0;

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

    for (int i = 0; i < cnedg; ++i) {
        if (comp[belong[nedg[i].first]] != comp[belong[nedg[i].second]]) {
            assert(cedg < 3 * max_N);
            edg[cedg] = nedg[i];
            ++cedg;
        } else {
            belong.unite(nedg[i].first, nedg[i].second);
        }
    }

    #ifdef DEBUG
        for (int i = 0; i < N; ++i) {
            std::cerr << belong[i] << " \n"[i == N - 1];
        }
        for (int i = 0; i < cedg; ++i) {
            std::cerr << edg[i].first + 1 << ' ' << edg[i].second + 1 << '\n';
        }
        std::cerr << '\n';
    #endif
}

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

    std::cin >> N >> M;

    while (M--) {
        std::cin >> A[cur] >> B[cur];
        --A[cur], --B[cur];
        ++cur;
        if (cur == S) {
            recalc();
        }
    }

    recalc();

    for (int i = 0; i < cedg; ++i) {
        std::cout << edg[i].first + 1 << ' ' << edg[i].second + 1 << '\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10