제출 #1081287

#제출 시각아이디문제언어결과실행 시간메모리
1081287jk_Pipes (CEOI15_pipes)C++14
0 / 100
2233 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100000; struct ufind { int *c; ufind(int *c) : c(c) { iota(c, c+N, 0); } int find(int k) { if (c[k] == k) return k; while (c[k] != c[c[k]]) c[k] = c[c[k]]; return c[k]; } void unite(int a, int b) { c[find(a)] = find(b); } }; struct edge { int to; int next; }; edge edges[4*N]; int edges_i = 0; int g[N]; int timer=0; int pre[N]; int low[N]; bitset<2*N> evis; void dfs(int v) { pre[v] = low[v] = timer++; for (;;) { int e = g[v]; if (e == -1) return; g[v] = edges[e].next; int w = edges[e].to; if (evis[e/2]) { continue; } evis[e/2] = true; if (pre[w] != -1) { low[v] = min(low[v], pre[w]); } else { dfs(w); low[v] = min(low[v], low[w]); if (low[w] > pre[v]) { cout << v+1 << ' ' << w+1 << '\n'; } } } }; int main() { fill(g, g+N, -1); int n, m; cin >> n >> m; assert(n <= N); { array<ufind, 2> msts{{ufind(pre), ufind(low)}}; for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; --a; --b; for (auto& mst : msts) { if (mst.find(a) != mst.find(b)) { mst.unite(a, b); edges[edges_i] = {b, g[a]}; g[a] = edges_i++; edges[edges_i] = {a, g[b]}; g[b] = edges_i++; break; } } } } fill(pre, pre+N, -1); fill(low, low+N, -1); if (N > 10000) return 0; for (int i = 0; i < n; ++i) if (pre[i] == -1) dfs(i); }
#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...