Submission #385758

#	Time	Username	Problem	Language	Result	Execution time	Memory
385758		erfanmir	Pipes (CEOI15_pipes)	C++17	100 / 100	1645 ms	13548 KiB

pipes

// In the name of god

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const int MAXN = 1e5 + 10;
const int MAXLG = 18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 8e18;
int n, m, par[2][MAXN], dp[MAXN], pr[MAXN], h[MAXN];
bool mark[MAXN];
vector<int> adj[MAXN];

int getroot(int ind, int v){
    if(par[ind][v] == v){
        return v;
    }
    return par[ind][v] = getroot(ind, par[ind][v]);
}

bool merg(int ind, int v, int u){
    v = getroot(ind, v);
    u = getroot(ind, u);
    if(v == u){
        return false;
    }
    par[ind][u] = v;
    return true;
}

void dfs(int v){
    mark[v] = true;
    for(auto u : adj[v]){
        if(!mark[u]){
            h[u] = h[v] + 1;
            pr[u] = v;
            dfs(u);
            dp[v] += dp[u];
        }
        else{
            if(h[v] > h[u]){
                dp[v]++;
                dp[u]--;
            }
        }
    }
    if(dp[v] == 1 && pr[v] != 0){
        printf("%d %d\n", v, pr[v]);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        par[0][i] = par[1][i] = i;
    }
    for(int i = 0; i < m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        if(merg(0, x, y)){
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        else{
            if(merg(1, x, y)){
                adj[x].push_back(y);
                adj[y].push_back(x);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(!mark[i]){
            h[i] = 1;
            dfs(i);
        }
    }
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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