Submission #1193892

#TimeUsernameProblemLanguageResultExecution timeMemory
1193892nuutsnoyntonPipes (CEOI15_pipes)C++20
30 / 100
387 ms16544 KiB
#include<bits/stdc++.h> using namespace std; using ll = int; using pll = pair < ll, ll >; const ll N = 1e4 + 2; ll tin[N], timer = 1, low[N]; vector < ll > adj[N]; void euler_tour(ll node, ll par) { tin[node] = timer; low[node] = timer; timer ++; bool parent_found = false; for ( ll nxt : adj[node]) { if ( nxt == par && parent_found == false) { parent_found = true; continue; } if ( tin[nxt] > 0) { low[node] = min(low[node], tin[nxt]); continue; } euler_tour(nxt, node); low[node] = min(low[node], low[nxt]); if ( low[nxt] > tin[node]) { cout << node << " " << nxt << endl; } } } ll ataman[N]; ll Get(ll x) { if ( x == ataman[x]) return x; return ataman[x] = Get(ataman[x]); } void Unite(ll x, ll y) { x = Get(x); y = Get(y); if (x == y) return ; if ( x > y) swap(x,y); ataman[x] = y; } int main() { ll n, m, r, x, y, i, j, ans, t; cin >> n >> m; for (i = 1; i <= n; i ++) ataman[i] = i; for (i = 1; i <= m; i ++) { cin >> x >> y; if ( Get(x) == Get(y)) continue; adj[x].push_back(y); adj[y].push_back(x); } for (i = 1; i <= n; i ++) { if ( tin[i] == 0) euler_tour(i, -1); } }
#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...