oj.uz

Submission #547273

# Submission time Handle Problem Language Result Execution time Memory
547273 2022-04-10T08:12:05 Z Jomnoi Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 127892 KB 
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MAX_N = 5e5 + 10;

set <pair <int, int>> graph[MAX_N];
bitset <MAX_N> visited;

bool dfs(int u, int x, int p) {
    if(visited[u] == true) {
        return u == x;
    }
    visited[u] = true;

    for(auto [v, i] : graph[u]) {
        if(v == p) {
            continue;
        }

        if(dfs(v, x, u) == true) {
            graph[u].erase(make_pair(v, i));
            graph[v].erase(make_pair(u, i));
            cout << u << ' ';
            return true;
        }
    }
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace(v, i);
        graph[v].emplace(u, i);
    }

    for(int i = 1; i <= n; i++) {
        while(!graph[i].empty()) {
            dfs(i, i, -1);
            cout << '\n';
            visited = 0;
        }
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 13 ms 23920 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 16 ms 24184 KB Output is correct
5 Correct 12 ms 23960 KB Output is correct
6 Correct 15 ms 24276 KB Output is correct
7 Correct 25 ms 25504 KB Output is correct
8 Correct 13 ms 24276 KB Output is correct
9 Correct 197 ms 34316 KB Output is correct
10 Correct 18 ms 24148 KB Output is correct
11 Correct 15 ms 24168 KB Output is correct
12 Correct 257 ms 34728 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23916 KB Output is correct
2 Correct 12 ms 23892 KB Output is correct
3 Correct 12 ms 23808 KB Output is correct
4 Correct 17 ms 24216 KB Output is correct
5 Correct 13 ms 24020 KB Output is correct
6 Correct 16 ms 24396 KB Output is correct
7 Correct 26 ms 25408 KB Output is correct
8 Correct 15 ms 24336 KB Output is correct
9 Correct 190 ms 34400 KB Output is correct
10 Correct 17 ms 24136 KB Output is correct
11 Correct 16 ms 24280 KB Output is correct
12 Correct 256 ms 34752 KB Output is correct
13 Correct 85 ms 44364 KB Output is correct
14 Correct 172 ms 39652 KB Output is correct
15 Correct 205 ms 34672 KB Output is correct
16 Correct 85 ms 44372 KB Output is correct
17 Correct 308 ms 34896 KB Output is correct
18 Correct 173 ms 37392 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 12 ms 23908 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 19 ms 24140 KB Output is correct
5 Correct 13 ms 24016 KB Output is correct
6 Correct 16 ms 24364 KB Output is correct
7 Correct 26 ms 25404 KB Output is correct
8 Correct 13 ms 24276 KB Output is correct
9 Correct 196 ms 34368 KB Output is correct
10 Correct 17 ms 24148 KB Output is correct
11 Correct 15 ms 24276 KB Output is correct
12 Correct 255 ms 34920 KB Output is correct
13 Correct 88 ms 44436 KB Output is correct
14 Correct 171 ms 39700 KB Output is correct
15 Correct 204 ms 34636 KB Output is correct
16 Correct 88 ms 44428 KB Output is correct
17 Correct 300 ms 35012 KB Output is correct
18 Correct 170 ms 37376 KB Output is correct
19 Correct 443 ms 127892 KB Output is correct
20 Execution timed out 953 ms 104436 KB Time limit exceeded
21 Halted 0 ms 0 KB -