oj.uz

Submission #1115996

# Submission time Handle Problem Language Result Execution time Memory
1115996 2024-11-21T07:27:22 Z vjudge1 Pipes (CEOI15_pipes) C++17
90 / 100
 2537 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;
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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9040 KB Output is correct
2 Correct 5 ms 9104 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9040 KB Output is correct
2 Correct 60 ms 9040 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 9720 KB Output is correct
2 Correct 116 ms 9296 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 10056 KB Output is correct
2 Correct 264 ms 10056 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 12580 KB Output is correct
2 Correct 295 ms 12616 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 13128 KB Output is correct
2 Correct 1075 ms 12244 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 14408 KB Output is correct
2 Correct 691 ms 14996 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 14584 KB Output is correct
2 Runtime error 815 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 14152 KB Output is correct
2 Correct 2537 ms 13028 KB Output is correct