Submission #442005

#	Time	Username	Problem	Language	Result	Execution time	Memory
442005		JovanB	Pipes (CEOI15_pipes)	C++17	100 / 100	1881 ms	15772 KiB

pipes

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

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

const int BLOCK = 60000;
const int MAXN = 100000;

vector <tuple <int, int, int>> graf[MAXN+5];
vector <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 x : graf[v]){
        int c = gde[get<0>(x)];
        if(c == v) c = gde[get<1>(x)];
        if(visited[c]){
            if(get<2>(x) == gr) continue;
            up[v] = min(up[v], up[c]);
        }
        else{
            dfs_bridges(c, get<2>(x));
            up[v] = min(up[v], up[c]);
        }
    }
}

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(p);
            swap(get<0>(p), get<1>(p));
            ngraf[lst].push_back(p);
        }
        sd = v;
    }
    else ide[v] = gde[lst];
    for(auto x : graf[v]){
        int c = gde[get<0>(x)];
        if(c == v) c = gde[get<1>(x)];
        if(!visited[c]) dfs_connect(c, x, 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;
            if(gde[a] == gde[b]) continue;
            ++svih;
            graf[gde[a]].push_back({a, b, svih});
            graf[gde[b]].push_back({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]];
            vector <tuple <int, int, int>>().swap(graf[i]);
            for(auto c : ngraf[i]) graf[i].push_back(c);
            vector <tuple <int, int, int>>().swap(ngraf[i]);
        }
        m -= BLOCK;
    }
    for(int i=1; i<=n; i++){
        for(auto c : graf[i]) if(get<0>(c) < get<1>(c)) cout << get<0>(c) << " " << get<1>(c) << "\n";
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10