Submission #518391

#	Time	Username	Problem	Language	Result	Execution time	Memory
518391		blue	Pipes (CEOI15_pipes)	C++17	50 / 100	252 ms	5276 KiB

pipes

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 30'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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10