oj.uz

Submission #1115968

# Submission time Handle Problem Language Result Execution time Memory
1115968 2024-11-21T06:42:08 Z vjudge1 Pipes (CEOI15_pipes) C++17
10 / 100
 255 ms 19596 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[2 * max_N], nedg[2 * 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 ^ nedg[i].first ^ nedg[i].second;
        if (tin[belong[u]] == -1) {
            tarjan(belong[u], i);
            low[v] = std::min(low[v], low[belong[u]]);
        } else if (comp[belong[u]] == -1) {
            low[v] = std::min(low[v], tin[belong[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) {
        adj[i].clear();
        tin[i] = low[i] = comp[i] = -1;
    }

    cnedg = 0;
    for (int i = 0; i < cur; ++i) {
        if (belong[A[i]] != belong[B[i]]) {
            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 < cedg; ++i) {
        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 < N; ++i) {
        if (tin[belong[i]] == -1) {
            tarjan(i, -1);
        }
    }

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

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();
        }
    }

    if (cur) {
        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 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7504 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 7504 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 8264 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 9288 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 17736 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 54 ms 18504 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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