Submission #1043350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043350		Pekiban	Pipes (CEOI15_pipes)	C++17	40 / 100	620 ms	46672 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';
        }
    }

• 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