oj.uz

Submission #385747

# Submission time Handle Problem Language Result Execution time Memory
385747 2021-04-04T21:10:45 Z erfanmir Pipes (CEOI15_pipes) C++17
50 / 100
 1500 ms 37868 KB 
// In the name of god

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
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], sz[2][MAXN], st[MAXN], dp[MAXN], cnt;
pii pr[MAXN];
bool mark[MAXN];
vector<pii> 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;
    }
    if(sz[ind][v] < sz[ind][u]){
        swap(v, u);
    }
    par[ind][u] = v;
    sz[ind][v] += sz[ind][u];
    return true;
}

void dfs(int v){
    st[v] = cnt++;
    dp[v] = v;
    mark[v] = true;
    for(auto u : adj[v]){
        if(!mark[u.S]){
            pr[u.S] = mp(u.F, v);
            dfs(u.S);
            if(st[dp[u.S]] < st[dp[v]]){
                dp[v] = dp[u.S];
            }
        }
        else{
            if(u.F == pr[v].F){
                continue;
            }
            if(st[u.S] < st[dp[v]]){
                dp[v] = u.S;
            }
        }
    }
    if(dp[v] == v && pr[v].S != 0){
        printf("%d %d\n", v, pr[v].S);
    }
}

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

Compilation message

pipes.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
pipes.cpp: In function 'int main()':
pipes.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |         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 2 ms 2668 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 8684 KB Output is correct
2 Correct 130 ms 8428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 13676 KB Output is correct
2 Correct 269 ms 15060 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 375 ms 22252 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 14316 KB Output is correct
2 Correct 442 ms 11244 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 770 ms 16460 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 993 ms 24036 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1218 ms 25580 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1500 ms 37868 KB Memory limit exceeded
2 Halted 0 ms 0 KB -