Submission #1043376

#TimeUsernameProblemLanguageResultExecution timeMemory
1043376PekibanPipes (CEOI15_pipes)C++17
50 / 100
597 ms42064 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back const int N = 1e5+5; mt19937 rng(time(0)); // upravo sam imao najgenijalniju ideju svih vremena vector<int> g[N]; int p[N], dp[N], vis[N]; int get(int x) { if (x == p[x]) return x; return p[x] = get(p[x]); } bool unite(int u, int v) { if (get(u) == get(v)) return 0; p[get(v)] = get(u); g[u].pb(v); g[v].pb(u); return 1; } void upd(int u, int v) { int x = rng() % (1LL << 31); dp[u] ^= x; dp[v] ^= x; } void dfs(int &s, int &e) { for (auto &u : g[s]) { if (u == e) continue; dfs(u, s); dp[s] ^= dp[u]; } if (e && !dp[s]) cout << e << ' ' << s << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); iota(p, p+N, 0); int n, m; cin >> n >> m; int u, v; for (int i = 0; i < m; ++i) { cin >> u >> v; if (!unite(u, v)) upd(u, v); } for (int i = 1; i <= n; ++i) { if (!vis[get(i)]) { int p = get(i), z = 0; dfs(p, z); vis[get(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...