oj.uz

Submission #540643

# Submission time Handle Problem Language Result Execution time Memory
540643 2022-03-21T10:19:43 Z Vladth11 Pipes (CEOI15_pipes) C++14
20 / 100
 1780 ms 65536 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 200001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 16;

vector <int> v[NMAX];
int root;
int dp[NMAX], lvl[NMAX];

void DFS(int node, int p){
    lvl[node] = lvl[p] + 1;
    for(auto x : v[node]){
        if(lvl[x] == 0){
            DFS(x, node);
            dp[node] += dp[x];
        }else if(lvl[x] > lvl[node]){
            dp[node]--;
        }else{
            dp[node]++;
        }
    }
    if(node != root){
        dp[node]--;
    }
    if(dp[node] == 0 && node != root){
        cout << node << " " << p << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, i;
    cin >> n >> m;
    for(i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i = 1; i <= n; i++){
        if(!lvl[i]){
            root = i;
            DFS(root, 0);
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5588 KB Output is correct
2 Correct 6 ms 5332 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1364 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1719 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1780 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -