oj.uz

Submission #518399

# Submission time Handle Problem Language Result Execution time Memory
518399 2022-01-23T16:07:29 Z blue Pipes (CEOI15_pipes) C++17
70 / 100
 655 ms 15932 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 80'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);
        }
    }
    edge[u].clear();
    ee.push_back(u);
    // cerr << "dfs exit " << u << '\n';
}

int ct = 0;

void dfs2(int u)
{
    visit[u] = ct;
    for(int v: rev_edge[u])
    {
        if(visit[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);
    }

    A.parent.clear();
    A.subtree.clear();
    B.parent.clear();
    B.subtree.clear();

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

    reverse(ee.begin(), ee.end());
    visit = vi(1+N, 0);

    for(int u: ee)
    {
        // cerr << "u = " << u << '\n';
        if(visit[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: rev_edge[u])
            if(visit[u] != visit[v])
                cout << u << ' ' << v << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6220 KB Output is correct
2 Correct 7 ms 5980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 6060 KB Output is correct
2 Correct 99 ms 5832 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 6800 KB Output is correct
2 Correct 176 ms 6420 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 8660 KB Output is correct
2 Correct 239 ms 8548 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 14612 KB Output is correct
2 Correct 396 ms 11536 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 15932 KB Output is correct
2 Correct 563 ms 13428 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 11212 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 8 ms 11252 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 12 ms 11268 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -