oj.uz

Submission #311620

# Submission time Handle Problem Language Result Execution time Memory
311620 2020-10-10T19:36:54 Z ly20 Pipes (CEOI15_pipes) C++17
40 / 100
 1862 ms 27084 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
vector <int> grafo[MAXN], id[MAXN];
int pai[MAXN], tam[MAXN], pai2[MAXN], tam2[MAXN];
vector <pair <int, int> > ar;
int low[MAXN], prof[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;
    if(tam[a] > tam[b]) {
        pai[b] = a;
        tam[a] += tam[b];
    }
    else {
        pai[a] = b;
        tam[b] += tam[a];
    }
}
void une2(int a, int b) {
    a = find2(a); b = find2(b);
    if(a == b) return;
    if(tam2[a] > tam2[b]) {
        pai2[b] = a;
        tam2[a] += tam2[b];
    }
    else {
        pai2[a] = b;
        tam2[b] += tam2[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; tam[i] = 1; pai2[i] = i; tam2[i] = 1;
    }
    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:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < grafo[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:76: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]
   76 |     for(int i = 0; i < ar.size(); i++) {
      |                    ~~^~~~~~~~~~~
pipes.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0; i < resp.size(); i++) printf("%d %d\n", ar[resp[i]].first, ar[resp[i]].second);
      |                    ~~^~~~~~~~~~~~~
pipes.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         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 5888 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 5880 KB Output is correct
2 Correct 165 ms 5812 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 6016 KB Output is correct
2 Correct 338 ms 6156 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 6608 KB Output is correct
2 Runtime error 390 ms 21364 KB Memory limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 8076 KB Output is correct
2 Runtime error 499 ms 26088 KB Memory limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 8424 KB Output is correct
2 Runtime error 908 ms 18924 KB Memory limit exceeded

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 12316 KB Output is correct
2 Runtime error 1427 ms 26604 KB Memory limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1862 ms 13428 KB Output is correct
2 Runtime error 1801 ms 27084 KB Memory limit exceeded