제출 #1080239

#제출 시각아이디문제언어결과실행 시간메모리
1080239jk_Pipes (CEOI15_pipes)C++11
40 / 100
2086 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100000; struct ufind { array<int, N>& c; ufind(array<int, N>& c) : c(c) { iota(c.begin(), c.end(), 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; }; array<edge, 4*N> edges; int edges_i = 0; array<int, N> g; int timer=0; array<int, N> pre; array<int, N> low; bitset<2*N> evis; void dfs(int v) { pre[v] = low[v] = timer++; for (int e = g[v]; e != -1; e = edges[e].next) { if (evis[e/2]) { continue; } evis[e/2] = true; if (pre[edges[e].to] != -1) { low[v] = min(low[v], pre[edges[e].to]); } else { dfs(edges[e].to); low[v] = min(low[v], low[edges[e].to]); if (low[edges[e].to] > pre[v]) { cout << v+1 << ' ' << edges[e].to+1 << '\n'; } } } } int main() { fill(g.begin(), g.end(), -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.begin(), pre.end(), -1); fill(low.begin(), low.end(), -1); 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...