oj.uz

답안 #518401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518401 2022-01-23T16:09:41 Z blue Pipes (CEOI15_pipes) C++17
70 / 100
 602 ms 16272 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 85'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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 5964 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 6564 KB Output is correct
2 Correct 8 ms 6280 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 6396 KB Output is correct
2 Correct 86 ms 6252 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 7140 KB Output is correct
2 Correct 165 ms 6740 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 8984 KB Output is correct
2 Correct 218 ms 8896 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 357 ms 14844 KB Output is correct
2 Correct 357 ms 11864 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 16272 KB Output is correct
2 Correct 514 ms 13772 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 11868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 11972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 11884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -