Submission #1204017

#TimeUsernameProblemLanguageResultExecution timeMemory
1204017petezaPipes (CEOI15_pipes)C++20
20 / 100
5097 ms77116 KiB
#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[1000005]; 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(yas, 0, sizeof yas); 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() == 1000000) { //do cleaning cleanedge(); assert(edge.size() <= 100000); } } cleanedge(); //cout << '\n'; for(auto &e:edge) cout << e.first.first << ' ' << e.first.second << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...