Submission #1347514

#TimeUsernameProblemLanguageResultExecution timeMemory
1347514tung04885Pipes (CEOI15_pipes)C++20
30 / 100
826 ms131072 KiB
#include <bits/stdc++.h>
using namespace std;
#define MAX 100100
#define MAXEDGE 6006006
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))

template<class X,class Y> bool maximize(X &x,Y y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}

template<class X,class Y> bool minimize(X &x,Y y)
{
    if(y<x)
    {
        x=y;
        return 1;
    }
    return 0;
}

const int inf=1e9+412009;
const ll INF=2e18+412009;

pii edge[MAXEDGE];
int n,m;
vector<int> adj[MAX];

void nhap()
{
    cin>>n>>m;

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

        edge[i]={u,v};

        adj[u].push_back(i);
        adj[v].push_back(i);
    }
}

int low[MAX]={},num[MAX]={},cnt=0;
bool used[MAXEDGE]={};

void dfs(int u)
{
    num[u]=++cnt;
    low[u]=n+1;

    for(int id:adj[u]) if(!used[id])
    {
        used[id]=1;

        int v=edge[id].fi+edge[id].se-u;

        if(num[v]==0)
        {
            dfs(v);

            minimize(low[u],low[v]);

            if(low[v]>num[u]) cout<<u<<' '<<v<<'\n';
        }
        else minimize(low[u],num[v]);
    }
}

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

    nhap();

    for(int i=1;i<=n;i++) if(num[i]==0) dfs(i);

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...