oj.uz

Submission #1115984

# Submission time Handle Problem Language Result Execution time Memory
1115984 2024-11-21T07:14:26 Z vjudge1 Pipes (CEOI15_pipes) C++17
70 / 100
 5000 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 = 2450;

int N, M;
std::vector<int> adj[max_N], ans;
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++;
    for (auto i : adj[v]) {
        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) {
        while (!adj[i].empty()) {
            adj[i].pop_back();
        }
        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 6 ms 9040 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 9040 KB Output is correct
2 Correct 64 ms 9212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 9296 KB Output is correct
2 Correct 122 ms 9296 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 10040 KB Output is correct
2 Correct 373 ms 10056 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 13384 KB Output is correct
2 Correct 422 ms 13836 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 14588 KB Output is correct
2 Correct 2011 ms 12596 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1108 ms 16364 KB Output is correct
2 Runtime error 1032 ms 59064 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1482 ms 16000 KB Output is correct
2 Execution timed out 5006 ms 65536 KB Time limit exceeded
3 Halted 0 ms 0 KB -