oj.uz

Submission #441996

# Submission time Handle Problem Language Result Execution time Memory
441996 2021-07-06T16:55:09 Z JovanB Pipes (CEOI15_pipes) C++17
60 / 100
 2077 ms 25464 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int BLOCK = 10000;
const int MAXN = 100000;

vector <pair <int, tuple <int, int, int>>> graf[MAXN+5];
vector <pair <int, tuple <int, int, int>>> ngraf[MAXN+5];
bool visited[MAXN+5];
int in[MAXN+5];
int up[MAXN+5];
int gde[MAXN+5];
int ide[MAXN+5];

int tjm;

void dfs_bridges(int v, int gr){
    visited[v] = 1;
    in[v] = ++tjm;
    up[v] = in[v];
    for(auto c : graf[v]){
        if(visited[c.first]){
            if(get<2>(c.second) == gr) continue;
            up[v] = min(up[v], up[c.first]);
        }
        else{
            dfs_bridges(c.first, get<2>(c.second));
            up[v] = min(up[v], up[c.first]);
        }
    }
}

void dfs_connect(int v, tuple <int, int, int> p, int lst){
    int sd = lst;
    visited[v] = 1;
    ide[v] = v;
    if(up[v] >= in[v]){
        if(lst){
            ngraf[v].push_back({lst, p});
            ngraf[lst].push_back({v, p});
        }
        sd = v;
    }
    else ide[v] = gde[lst];
    for(auto c : graf[v]){
        if(!visited[c.first]) dfs_connect(c.first, c.second, sd);
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        gde[i] = i;
    }
    int svih = 0;
    while(m > 0){
        for(int i=1; i<=min(m, BLOCK); i++){
            int a, b;
            cin >> a >> b;
            ++svih;
            graf[gde[a]].push_back({gde[b], {a, b, svih}});
            graf[gde[b]].push_back({gde[a], {b, a, svih}});
        }
        tjm = 0;
        for(int i=1; i<=n; i++) visited[i] = 0;
        for(int i=1; i<=n; i++) ngraf[i].clear();
        for(int i=1; i<=n; i++){
            if(!visited[gde[i]]) dfs_bridges(gde[i], 0);
        }
        for(int i=1; i<=n; i++) visited[i] = 0;
        for(int i=1; i<=n; i++){
            if(!visited[gde[i]]) dfs_connect(gde[i], {0, 0, 0}, 0);
        }
        for(int i=1; i<=n; i++){
            gde[i] = ide[gde[i]];
            graf[i].clear();
            for(auto c : ngraf[i]) graf[i].push_back(c);
            ngraf[i].clear();
        }
        m -= BLOCK;
    }
    vector <pair <int, int>> results;
    for(int i=1; i<=n; i++){
        for(auto c : graf[i]) results.push_back({get<0>(c.second), get<1>(c.second)});
    }
    sort(results.begin(), results.end());
    for(int i=0; i<results.size(); i++) if(i == 0 || results[i] != results[i-1]) cout << results[i].first << " " << results[i].second << "\n";
    return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0; i<results.size(); i++) if(i == 0 || results[i] != results[i-1]) cout << results[i].first << " " << results[i].second << "\n";
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6056 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 133 ms 11244 KB Output is correct
2 Correct 138 ms 11172 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 12264 KB Output is correct
2 Correct 291 ms 11788 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 14388 KB Output is correct
2 Correct 436 ms 15812 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 15836 KB Output is correct
2 Correct 631 ms 15328 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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