oj.uz

Submission #518394

# Submission time Handle Problem Language Result Execution time Memory
518394 2022-01-23T15:59:54 Z blue Pipes (CEOI15_pipes) C++17
60 / 100
 393 ms 14040 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 70'000;
using vi = vector<int>;

struct disjoint_set
{
public:
    vi parent = vi(1+mx);
    vi subtree = vi(1+mx, 1);

    disjoint_set()
    {
        for(int i = 1; i <= mx; i++) parent[i] = i;
    }

    int root(int u)
    {
        if(parent[u] == u) return u;
        else return (parent[u] = root(parent[u]));
    }

    bool join(int u, int v)
    {
        u = root(u);
        v = root(v);

        if(u == v) return 0;

        if(subtree[u] < subtree[v]) swap(u, v);
        parent[v] = u;
        subtree[u] += subtree[v];

        return 1;
    }
};

vi edge[1+mx];

void add_edge(int u, int v)
{
    edge[u].push_back(v);
    edge[v].push_back(u);
    // cerr << "adding edge " << u << ' ' << v << '\n';
}

vi rev_edge[1+mx];
vi visit(1+mx, 0);

vi ee;

void dfs(int u, int p)
{
    // cerr << "dfs enter " << u << '\n';
    visit[u] = 1;
    int cont = 0;
    for(int v: edge[u])
    {
        if(cont == 0 && v == p)
        {
            cont++;
            continue;
        }

        if(visit[v])
        {
            rev_edge[v].push_back(u);
        }
        else
        {
            rev_edge[v].push_back(u);
            dfs(v, u);
        }
    }
    ee.push_back(u);
    // cerr << "dfs exit " << u << '\n';
}

int ct = 0;
vi bcc(1+mx, 0);

void dfs2(int u)
{
    bcc[u] = ct;
    for(int v: rev_edge[u])
    {
        if(bcc[v]) continue;
        dfs2(v);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    disjoint_set A;
    disjoint_set B;

    for(int e = 1; e <= M; e++)
    {
        int u, v;
        cin >> u >> v;

        if(A.join(u, v)) add_edge(u, v);
        else if(B.join(u, v)) add_edge(u, v);
    }

    for(int u = 1; u <= N; u++)
    {
        if(visit[u]) continue;
        dfs(u, 0);
    }

    reverse(ee.begin(), ee.end());

    for(int u: ee)
    {
        // cerr << "u = " << u << '\n';
        if(bcc[u]) continue;
        ct++;
        dfs2(u);
    }

    // for(int i = 1; i <= N; i++) cerr << bcc[i] << ' ';
    // cerr << '\n';

    for(int u = 1; u <= N; u++)
        for(int v: edge[u])
            if(v > u && bcc[u] != bcc[v])
                cout << u << ' ' << v << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5836 KB Output is correct
2 Correct 6 ms 5520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5656 KB Output is correct
2 Correct 86 ms 5532 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 6432 KB Output is correct
2 Correct 176 ms 6140 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 8136 KB Output is correct
2 Correct 238 ms 7996 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 14040 KB Output is correct
2 Correct 393 ms 11144 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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