oj.uz

Submission #385758

# Submission time Handle Problem Language Result Execution time Memory
385758 2021-04-04T22:04:48 Z erfanmir Pipes (CEOI15_pipes) C++17
100 / 100
 1645 ms 13548 KB 
// 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3180 KB Output is correct
2 Correct 7 ms 2924 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 3052 KB Output is correct
2 Correct 138 ms 2924 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 3820 KB Output is correct
2 Correct 262 ms 3436 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 5228 KB Output is correct
2 Correct 330 ms 4972 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 10348 KB Output is correct
2 Correct 452 ms 7404 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 11500 KB Output is correct
2 Correct 779 ms 8972 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 13540 KB Output is correct
2 Correct 988 ms 9432 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1311 ms 13548 KB Output is correct
2 Correct 1219 ms 9536 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1645 ms 12896 KB Output is correct
2 Correct 1541 ms 10732 KB Output is correct