Submission #1034752

#TimeUsernameProblemLanguageResultExecution timeMemory
1034752vjudge1Pipes (CEOI15_pipes)C++17
40 / 100
706 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5+2; struct dsu { int e[N]; int find(int &x) { return e[x] < 0 ? x : e[x] = find(e[x]); } bool join(int a, int b) { a = find(a), b = find(b); if (a == b) return false; if (e[a] > e[b]) swap(a, b); e[a] += e[b]; e[b] = a; return true; } } d1, d2; vector<int> g[N]; int timer=0; void dfs(int &at, int &par) { d1.e[at]=d2.e[at]=++timer; for(int &to:g[at]) { if(to == par) { par+=N; continue; } if(d2.e[to]) { d1.e[at]=min(d1.e[at], d2.e[to]); } else { dfs(to, at); d1.e[at]=min(d1.e[at], d1.e[to]); } } if(par>N)par-=N; if(d1.e[at] == d2.e[at] and at!=par) { cout << at << " " << par << "\n"; } } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); srand(time(0)); int n, m; cin >> n >> m; int u, v; for(int i = 1;i<N;i++)d1.e[i]=d2.e[i]=-1; for(int i = 0;i<m;i++) { cin >> u >> v; if(d1.join(u, v) || d2.join(u, v)) { g[u].push_back(v); g[v].push_back(u); } } for(int i = 1;i<N;i++)d1.e[i]=d2.e[i]=0; for(int i= 1;i<=n;i++) { if(!d1.e[i]) { dfs(i, 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...