oj.uz

Submission #878731

# Submission time Handle Problem Language Result Execution time Memory
878731 2023-11-25T06:38:44 Z Ghulam_Junaid Pipes (CEOI15_pipes) C++17
20 / 100
 1079 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, p, h[N], mnh[N], st[N], ft[N], tme;

bool vis[N];
vector<pair<int, int>> g[N], edges, important;
string s;

bool in_sub(int u, int v){
    return (st[v] <= st[u] && st[u] < ft[v]);
}

void dfs(int v, int prev = -1){
    vis[v] = 1;
    mnh[v] = h[v];

    st[v] = tme;
    tme++;

    // cout << "Running dfs on " << v << endl;

    for (auto [id, u] : g[v]){
        if (id == prev) continue;

        if (!vis[u]){
            h[u] = h[v] + 1;
            dfs(u, id);
            mnh[v] = min(mnh[v], mnh[u]);

            if (mnh[u] > h[v]){ // (v, u) is a bridge
                cout << u << " " << v << endl;
                // cout << v << " -- " << u << " is a bridge." << endl;
            //     for (auto [x, y] : important){
            //         bool A = in_sub(x, u);
            //         bool B = in_sub(y, u);

            //         // cout << x << " " << y << " " << u << " " << A << " " << B << endl;

            //         if (A and !B){
            //             // u to v
            //             if (edges[id].first == u)
            //                 s[id] = 'R';
            //             else
            //                 s[id] = 'L';
            //         }
            //         if (!A and B){
            //             // v to u
            //             if (edges[id].first == v)
            //                 s[id] = 'R';
            //             else
            //                 s[id] = 'L';
            //         }
            //     }
            }
            // else
            //     s[id] = 'B';
        }
        else
            mnh[v] = min(mnh[v], h[u]);
    }
    ft[v] = tme;
}

int main(){
    cin >> n >> m;

    for (int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;

        s += 'B';
        edges.push_back({u, v});
        // if (u == v)
        //     continue;

        g[u].push_back({i, v});
        g[v].push_back({i, u});

    }

    for (int i=1; i<=n; i++)
        h[i] = mnh[i] = n + 100;

    // cin >> p;
    // for (int i=0; i<p; i++){
    //     int u, v;
    //     cin >> u >> v;

    //     // if (u == v) continue;
    //     important.push_back({u, v});
    // }

    for (int v = 1; v <= n; v++)
        if (!vis[v])
            dfs(v);

    // cout << s << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1018 ms 65536 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 1033 ms 65536 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 1008 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -