Submission #1204015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204015		peteza	Pipes (CEOI15_pipes)	C++20	20 / 100	5095 ms	24868 KiB

pipes

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b;
vector<pair<pair<int, int>, int>> edge;
vector<pair<pair<int, int>, int>> newedge;
int par[100005];
bool vis[100005], yas[200005];
int id[100005], c_id = 1, low[100005];
vector<pair<int, int>> adj[100005];
stack<int> stk;

int fpar(int x) {
    return (x == par[x] ? x : (par[x] = fpar(par[x])));
}

void dfs(int x, int paredge) {
    id[x] = low[x] = c_id++;
    int c_mx = -1;
    stk.push(x);
    //cout << x;
    for(auto &e:adj[x]) {
        if(e.second == paredge) continue;
        if(id[e.first]) low[x] = min(low[x], id[e.first]);
        else {
            dfs(e.first, e.second);
            low[x] = min(low[x], low[e.first]);
            c_mx = max(c_mx, low[e.first]);
        }
    }
    if(id[x] == low[x]) {
        if(paredge != 999999999) {
            //cout << "yes " << x << " and edge no. " << paredge << '\n';
            yas[paredge] = 1;
        }
        while(stk.top() != x) {
            int e = stk.top(); stk.pop();
            par[fpar(e)] = fpar(x);
        }
        stk.pop();
    }
    //if(c_mx >= id[x] && paredge != 999999999) yas[paredge] = 1;
}

void cleanedge() {
    memset(vis, 0, sizeof vis); memset(id, 0, sizeof id);
    for(auto e:edge) {
        e.first.first = fpar(e.first.first); e.first.second = fpar(e.first.second);
        adj[e.first.first].emplace_back(e.first.second, e.second);
        adj[e.first.second].emplace_back(e.first.first, e.second);
    }
    for(int i=1;i<=n;i++) {
        if(vis[fpar(i)]) continue;
        dfs(fpar(i), 999999999);
    }
    newedge.clear(); int bruh = 0;
    for(auto &e:edge) {
        if(yas[e.second]) {
            newedge.emplace_back(e.first, bruh++);
        }
    }
    edge = newedge;
    for(int i=1;i<=n;i++) adj[i].clear();
}

int main() {
    //cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) par[i] = i;
    while(m--) {
        cin >> a >> b;
        edge.emplace_back(pair<int, int>(a, b), edge.size());
        if(edge.size() == 200000) {
            //do cleaning
            cleanedge();
        }
    }
    cleanedge();
    //cout << '\n';
    for(auto &e:edge) cout << e.first.first << ' ' << e.first.second << '\n';

}

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