oj.uz

답안 #540701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540701 2022-03-21T12:39:56 Z Vladth11 Pipes (CEOI15_pipes) C++14
100 / 100
 1031 ms 12940 KB 
#include <bits/stdc++.h>
#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 = 100001;
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];
int parent[NMAX];
int parentB[NMAX];
 
int findR(int a){
    if(parent[a] == a)
        return a;
    return parent[a] = findR(parent[a]);
}
 
int findRB(int a){
    if(parentB[a] == a)
        return a;
    return parentB[a] = findRB(parentB[a]);
}
 
void unite(int a, int b){
    a = findR(a);
    b = findR(b);
    parent[a] = b;
}
 
void uniteB(int a, int b){
    a = findRB(a);
    b = findRB(b);
    parentB[a] = b;
}
 
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 <= n; i++){
        parent[i] = i;
        parentB[i] = i;
    }
    for(i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        if(findR(a) != findR(b)){
            v[a].push_back(b);
            v[b].push_back(a);
            unite(a, b);
        }else if(findRB(a) != findRB(b)){
            v[a].push_back(b);
            v[b].push_back(a);
            uniteB(a, b);
        }
    }
    for(i = 1; i <= n; i++){
        if(!lvl[i]){
            root = i;
            DFS(root, 0);
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3028 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 2964 KB Output is correct
2 Correct 83 ms 2840 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 3640 KB Output is correct
2 Correct 162 ms 3240 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 5204 KB Output is correct
2 Correct 212 ms 4784 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 342 ms 9860 KB Output is correct
2 Correct 375 ms 7020 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 531 ms 11024 KB Output is correct
2 Correct 492 ms 8524 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 741 ms 12940 KB Output is correct
2 Correct 643 ms 8864 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 971 ms 12940 KB Output is correct
2 Correct 805 ms 8860 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1031 ms 12432 KB Output is correct
2 Correct 941 ms 9964 KB Output is correct