oj.uz

Submission #1042776

# Submission time Handle Problem Language Result Execution time Memory
1042776 2024-08-03T11:21:11 Z otot Pipes (CEOI15_pipes) C++14
40 / 100
 640 ms 65536 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';    }}

Compilation message

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3416 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 54 ms 8576 KB Output is correct
2 Correct 63 ms 8576 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 13136 KB Output is correct
2 Correct 102 ms 14932 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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