oj.uz

Submission #311621

# Submission time Handle Problem Language Result Execution time Memory
311621 2020-10-10T19:39:26 Z ly20 Pipes (CEOI15_pipes) C++17
100 / 100
 2051 ms 11160 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
vector <int> grafo[MAXN], id[MAXN];
int pai[MAXN], pai2[MAXN];
vector <pair <int, int> > ar;
int low[MAXN], t, tp[MAXN];
vector <int> resp;
int find(int v) {
    if(v == pai[v]) return v;
    return pai[v] = find(pai[v]);
}
int find2(int v) {
    if(v == pai2[v]) return v;
    return pai2[v] = find2(pai2[v]);
}
void une(int a, int b) {
    a = find(a); b = find(b);
    if(a == b) return;
    pai[b] = a;
}
void une2(int a, int b) {
    a = find2(a); b = find2(b);
    if(a == b) return;
    pai2[b] = a;
}
void dfs(int v, int p) {
    tp[v] = ++t;
    low[v] = tp[v];
    for(int i = 0; i < grafo[v].size(); i++) {
        int viz = grafo[v][i], at = id[v][i];
        if(at == p) continue;
        if(tp[viz] != 0) {
            low[v] = min(low[v], tp[viz]);
        }
        else {
            dfs(viz, at);
            low[v] = min(low[v], low[viz]);
            if(low[viz] > tp[v]) {
                resp.push_back(at);
            }
        }
    }
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        pai[i] = i; pai2[i] = i;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        if(find(a) == find(b)) {
            une2(a, b);
            continue;
        }
        une(a, b);
        ar.push_back(make_pair(a, b));
    }
    //printf("\n\n");
    for(int i = 0; i < ar.size(); i++) {
        int a = find2(ar[i].first), b = find2(ar[i].second);
        if(a == b) continue;
        grafo[a].push_back(b); grafo[b].push_back(a);
        id[a].push_back(i); id[b].push_back(i);
        //printf("%d %d\n", ar[i].first, ar[i].second);
        //printf("%d %d\n", a, b);
    }
    //printf("\n\n");
    for(int i = 1; i <= n; i++) {
        if(tp[i] == 0) dfs(i, -1);
    }
    for(int i = 0; i < resp.size(); i++) printf("%d %d\n", ar[resp[i]].first, ar[resp[i]].second);
    return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0; i < grafo[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < ar.size(); i++) {
      |                    ~~^~~~~~~~~~~
pipes.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < resp.size(); i++) printf("%d %d\n", ar[resp[i]].first, ar[resp[i]].second);
      |                    ~~^~~~~~~~~~~~~
pipes.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5760 KB Output is correct
2 Correct 8 ms 5836 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 5752 KB Output is correct
2 Correct 164 ms 5752 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 6008 KB Output is correct
2 Correct 344 ms 6008 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 6288 KB Output is correct
2 Correct 422 ms 7464 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 7404 KB Output is correct
2 Correct 525 ms 7512 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 7656 KB Output is correct
2 Correct 1026 ms 9944 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 8168 KB Output is correct
2 Correct 1187 ms 10220 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1563 ms 8168 KB Output is correct
2 Correct 1490 ms 8172 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1923 ms 7912 KB Output is correct
2 Correct 2051 ms 11160 KB Output is correct