Submission #1326391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326391		arshiad	Pipes (CEOI15_pipes)	C++20	20 / 100	678 ms	14204 KiB

pipes

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
// #define int long long
#define ld long double
#define ll long long
#define pii pair <int, int>
#define pb push_back
#define fi first
#define se second
#define lc id * 2 + 0
#define rc id * 2 + 1
#define migmig ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);


const int maxn = 2e5 + 100;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int lg = 20;



int n, m;
int sz1[maxn], par1[maxn];
int sz2[maxn], par2[maxn];
vector <pii> ans;
vector <int> g[maxn];
bool vis[maxn];
int h[maxn], ps[maxn], par[maxn];


int find1(int u){
    return par1[u] == u ? u : par1[u] = find1(par1[u]);
}
int find2(int u){
    return par2[u] == u ? u : par2[u] = find2(par2[u]);
}


bool Union1(int u, int v){
    u = find1(u), v = find1(v);
    if (u == v)
        return 0;
    if (sz1[u] < sz1[v])
        swap(u, v);
    sz1[u] += sz1[v];
    par1[v] = u;
    return 1;
}
bool Union2(int u, int v){
    u = find2(u), v = find2(v);
    if (u == v)
        return 0;
    if (sz2[u] < sz2[v])
        swap(u, v);
    sz2[u] += sz2[v];
    par2[v] = u;
    return 1;
}


void DFS(int u){
    vis[u] = 1;
    for (auto v : g[u]){
        if (v == par[u])
            continue;
        if (vis[v]){
            if (h[u] > h[v]){
                ps[u] ++;
                ps[v] --;
            }
            continue;
        }

        par[v] = u;
        h[v] = h[u] + 1;
        DFS(v);
        ps[u] += ps[v];
    }
}


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

    for (int i = 1 ; i <= n ; i ++){
        par1[i] = par2[i] = i;
        sz1[i] = sz2[i] = 1;
    }

    for (int i = 1 ; i <= m ; i ++){
        int u, v;
        cin >> u >> v;
        if (Union1(u, v)){
            g[u].pb(v);
            g[v].pb(u);
        }
        else if (Union2(u, v)){
            g[u].pb(v);
            g[v].pb(u);
        }
    }

    for (int i = 1 ; i <= n ; i ++)
        if (!vis[i])
            DFS(i);

    for (int i = 1 ; i <= n ; i ++){
        if (par[i] == 0)
            continue;
        if (ps[i] == 0)
            ans.pb({i, par[i]});
    }

    for (auto [u, v] : ans)
        cout << u << ' ' << v << '\n';
}



int32_t main(){ migmig;
    int tt = 1;
    // cin >> tt;
    while (tt--)
        solve();
    return 0;
}

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