| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1042773 |
2024-08-03T11:19:30 Z |
otot |
Pipes (CEOI15_pipes) |
C++14 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>using namespace std;#define pb push_backconst int N = 1e5+5;mt19937 rng(time(0));// upravo sam imao najgenijalniju ideju svih vremena
vector<int> g[N];int p[N];long long dp[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) { long long x = rng() % (1LL << 62); dp[u] ^= x; dp[v] ^= x;}vector<array<int, 2>> ans;void dfs(int s, int e = 0) { for (auto u : g[s]) { if (u == e) continue; dfs(u, s); dp[s] ^= dp[u]; } if (e && !dp[s]) ans.pb({e, s});}bitset<N> vis;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)]) { dfs(get(i)); vis[get(i)] = 1; } } // for (int i = 1; i <= n; ++i) { // cout << i << ':'; // for (auto x : g[i]) { // cout << x << ' '; // } // cout << '\n'; // }
for (auto &[x, y] : ans) { if (x > y) swap(x, y); } sort(ans.begin(), ans.end()); for (auto [x, y] : ans) { cout << x << ' ' << y << '\n'; }}
Compilation message
pipes.cpp:1:31: warning: extra tokens at end of #include directive
1 | #include <bits/stdc++.h>using namespace std;#define pb push_backconst int N = 1e5+5;mt19937 rng(time(0));// upravo sam imao najgenijalniju ideju svih vremena
| ^~~~~~~~~
pipes.cpp:1:10: fatal error: bits/stdc++.h>usin: No such file or directory
1 | #include <bits/stdc++.h>using namespace std;#define pb push_backconst int N = 1e5+5;mt19937 rng(time(0));// upravo sam imao najgenijalniju ideju svih vremena
| ^~~~~~~~~~~~~~~~~~~~
compilation terminated.
