Submission #1150420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150420		SSSM	Pipes (CEOI15_pipes)	C++20	50 / 100	1887 ms	21928 KiB

pipes

#include <bits/stdc++.h>
 
/*
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
*/
 
using namespace std;
 
/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
 
#define F first
#define S second
#define pb push_back
#define md(a) ((a%mod+mod)%mod)
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc (id<<1)
#define rc (lc|1)
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
#define SZ(a) (ll)a.size()
 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64  rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll const maxn=1e5+10, mod=1e9+7, INF=1e18, LOG=31, sq=65;
 
ll poww(ll a, ll b, ll mod) {
 if (b == 0) return 1;
 return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}

ll n, m, par0[maxn], par1[maxn], sz0[maxn], sz1[maxn], h[maxn], low[maxn];
vector<pll> g[maxn];

void DSU()
{
    for(ll i=0;i<maxn;i++) {
        par0[i]=par1[i]=i;
       // sz0[i]=sz1[i]=i;
    }
}

ll Find0(ll v) {return par0[v]==v?v:par0[v]=Find0(par0[v]);}
ll Find1(ll v) {return par1[v]==v?v:par1[v]=Find1(par1[v]);}

bool Union(ll v, ll u)
{
    ll v0, u0;
    if((v0=Find0(v))==(u0=Find0(u))){
        ll v1, u1;
        if((v1=Find1(v))==(u1=Find1(u))) return 0;
        if(sz1[v1]<sz1[u1]) swap(v1, u1);
        par1[u1]=v1;
        sz1[v1]+=sz1[u1];
        return 1;
    }

    if(sz0[v0]<sz0[u0]) swap(v0, u0);
    par0[u0]=v0;
    sz0[v0]+=sz0[u0];
    return 1;
}

void DFS(ll v, ll p=0, ll lst=0)
{
    h[v]=h[p]+1;
    low[v]=h[v];
    for(auto [u, id]:g[v])
    {
        if(id==lst) continue;
        if(!h[u]) DFS(u, v, id);
        low[v]=min(low[v], low[u]);
    }
    if(low[v]==h[v] && p!=0)
    {
        cout<<v<<" "<<p<<"\n";
    }
}

int main() {

    cin>>n>>m;
    DSU();
    for(ll i=1;i<=m;i++)
    {
        ll v, u;
        cin>>v>>u;
        if(Union(v, u)){
            g[v].pb({u, i});
            g[u].pb({v, i});
        }
    }

    for(ll i=1;i<=n;i++)
    {
        if(!h[i]) DFS(i);
    }

	return 0;
}

• 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