oj.uz

Submission #503878

# Submission time Handle Problem Language Result Execution time Memory
503878 2022-01-09T06:15:26 Z CraniXort Pipes (CEOI15_pipes) C++17
40 / 100
 2211 ms 65540 KB 
#include <bits/stdc++.h>
#define maxn 100005

#define fin std::cin
#define fout std::cout

// std::ifstream fin("pipes.in");
// std::ofstream fout("pipes.out");

std::vector <int> edge[maxn];
int disc[maxn], low[maxn], timer;
bool visited[maxn];
std::vector <std::pair <int, int>> bridges;

void dfs(int node, int parent) {
    visited[node] = true;
    disc[node] = low[node] = ++timer;

    bool ok = false;

    for(auto next: edge[node]) {
        if(next == parent and ok == false) {
            ok = true;
            continue;
        }
        if(visited[next] == false) {
            dfs(next, node);
            low[node] = std::min(low[node], low[next]);

            if(low[next] > disc[node]) {
                bridges.push_back({node, next});
            }
        }
        else{
            low[node] = std::min(low[node], disc[next]);
        }
    }
}

class DSU {
    int size;
    std::vector <int> rank, parent;

    public:
    DSU(int size): size(size) {
        rank.resize(size+1);
        parent.resize(size+1);

        for(int i = 1; i <= size; i ++)
            parent[i] = i;
    }

    int findRoot(int node) {
        if(parent[node] == node)
            return node;
        return parent[node] = findRoot(parent[node]);
    }

    void combine(int node1, int node2) {
        node1 == findRoot(node1);
        node2 == findRoot(node2);
        if(node1 == node2)
            return;

        if(rank[node1] < rank[node2])
            std::swap(node1, node2);

        parent[node2] = node1;

        if(rank[node1] == rank[node2])
            rank[node1] ++;
    }

    bool sameComponent(int node1, int node2) {
        node1 = findRoot(node1);
        node2 = findRoot(node2);
        return node1 == node2;
    }
};

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

    int V, E;
    fin >> V >> E;

    DSU first(V), second(V);

    for(int i = 0, src, dest; i < E; i ++) {
        fin >> src >> dest;

        if(first.sameComponent(src, dest) == false) {
            edge[src].push_back(dest);
            edge[dest].push_back(src);
            first.combine(src, dest);
        }
        else if(second.sameComponent(src, dest) == false) {
            edge[src].push_back(dest);
            edge[dest].push_back(src);
            second.combine(src, dest);
        }
    }

    for(int i = 1; i <= V; i ++)
        if(visited[i] == false)
            dfs(i, -1);

    for(auto i: bridges)
        fout << i.first << ' ' << i.second << '\n';

    return 0;
}

Compilation message

pipes.cpp: In member function 'void DSU::combine(int, int)':
pipes.cpp:60:15: warning: value computed is not used [-Wunused-value]
   60 |         node1 == findRoot(node1);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~
pipes.cpp:61:15: warning: value computed is not used [-Wunused-value]
   61 |         node2 == findRoot(node2);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 5 ms 3020 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5092 KB Output is correct
2 Correct 90 ms 4052 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 9492 KB Output is correct
2 Correct 194 ms 7348 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 405 ms 20524 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 661 ms 33636 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1127 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1595 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1909 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2211 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -