oj.uz

Submission #1043350

# Submission time Handle Problem Language Result Execution time Memory
1043350 2024-08-04T08:41:32 Z Pekiban Pipes (CEOI15_pipes) C++17
40 / 100
 620 ms 46672 KB 
    #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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6204 KB Output is correct
2 Correct 50 ms 5968 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 8692 KB Output is correct
2 Correct 105 ms 9440 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 12372 KB Output is correct
2 Runtime error 134 ms 18228 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 16208 KB Output is correct
2 Runtime error 196 ms 24144 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 23068 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 396 ms 29264 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 497 ms 35232 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 620 ms 46672 KB Memory limit exceeded
2 Halted 0 ms 0 KB -