Submission #1042776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042776		otot	Pipes (CEOI15_pipes)	C++14	40 / 100	640 ms	65536 KiB

pipes

#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];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 (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:7:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
    7 | 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';    }}
      |            ^
pipes.cpp:7:110: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
    7 | 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';    }}
      |                                                                                                              ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10