oj.uz

Submission #385751

# Submission time Handle Problem Language Result Execution time Memory
385751 2021-04-04T21:19:25 Z erfanmir Pipes (CEOI15_pipes) C++17
70 / 100
 1611 ms 26988 KB 
// In the name of god

#pragma comment(linker, "/stack:200000000")
#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], 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;
    }
    par[ind][u] = v;
    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;
    }
    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:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         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 3308 KB Output is correct
2 Correct 9 ms 3052 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 3180 KB Output is correct
2 Correct 131 ms 3052 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 3908 KB Output is correct
2 Correct 257 ms 3564 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 5868 KB Output is correct
2 Runtime error 349 ms 19308 KB Memory limit exceeded

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 12140 KB Output is correct
2 Correct 512 ms 9068 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 13388 KB Output is correct
2 Correct 779 ms 12652 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 15980 KB Output is correct
2 Correct 991 ms 15340 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1326 ms 15980 KB Output is correct
2 Runtime error 1214 ms 26988 KB Memory limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1611 ms 15180 KB Output is correct
2 Runtime error 1602 ms 25184 KB Memory limit exceeded