Submission #1311848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311848		888313666	Pipes (CEOI15_pipes)	C++20	30 / 100	1158 ms	95824 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ <<' '<<
#define print(x) cout<<#x<<": "<<(x)<<'\n'

int n,m,c=-1;
vector<vector<int>> adj;
vector<int> low, num;
vector<pair<int, int>> bg;

void dfs(const int u, const int p) {
    low[u]=num[u]=++c;
    bool flag=0;
    for (const auto v:adj[u]) {
        if (v==p && !flag) {
            flag=1;
            continue;
        }
        if (num[v]==-1) {
            dfs(v, u);
            low[u]=min(low[u], low[v]);
            if (low[v]>num[u]) bg.push_back({u, v});
        }
        low[u]=min(low[u], num[v]);
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>m;
    adj.resize(n);
    for (int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        adj[--a].push_back(--b);
        adj[b].push_back(a);
    }
    low.assign(n, -1);
    num.assign(n, -1);
    for (int i=0; i<n; i++) if (num[i]==-1) dfs(i, i);
    for (const auto &[a, b]:bg) {
        cout<<a+1 _ b+1<<'\n';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10