oj.uz

Submission #412793

# Submission time Handle Problem Language Result Execution time Memory
412793 2021-05-27T14:26:01 Z fvogel499 Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 71444 KB 
/*
File created on 05/27/2021 at 15:50:04.
Link to problem: https://oj.uz/problem/view/BOI14_postmen
Description: Hierholzer's algorithm for eulerian cycle + separation in "mini" cycles
Time complexity: O(N+M)
Space complexity: O(N+M)
Status: DEV
Copyright: Ⓒ 2021 Francois Vogel
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define pib pair<int, *obj>
#define f first
#define s second

#define pb push_back
#define ins insert

#define int ll
#define ll long long

int encode(int a, int b) { return (min(a, b)*1000000+max(a, b)); }

signed main() {
    cin.tie(0);
    // ios_base::sync_with_stdio(0);

    int n, nbEdges;
    cin >> n >> nbEdges;

    vector<vector<int>> graph(n);
    for (int i = 0; i < nbEdges; i++) {
        int nodeA, nodeB;
        cin >> nodeA >> nodeB;
        nodeA--;
        nodeB--;
        graph[nodeA].pb(nodeB);
        graph[nodeB].pb(nodeA);
    }

    unordered_set<int> usedEdges;
    vector<int> circuit;
    vector<int> path;
    path.pb(0);
    while (!path.empty()) {
        while (!graph[path.back()].empty() and usedEdges.find(encode(path.back(), graph[path.back()].back())) != usedEdges.end()) graph[path.back()].pop_back();
        if (graph[path.back()].empty()) {
            circuit.pb(path.back());
            path.pop_back();
        }
        else {
            int nn = graph[path.back()].back();
            graph[path.back()].pop_back();
            usedEdges.insert(encode(path.back(), nn));
            path.pb(nn);
        }
    }

    bool as [n];
    memset(as, false, n);
    stack<int> st;
    for (int i : circuit) {
        if (as[i]) {
            while (st.top() != i) {
                as[st.top()] = false;
                cout << st.top()+1 << " ";
                st.pop();
            }
            st.pop();
            cout << i+1 << " " << endl;
        }
        as[i] = true;
        st.push(i);
    }

    int d = 0;
    d++;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 5 ms 620 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 4 ms 780 KB Output is correct
7 Correct 14 ms 1868 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 98 ms 10280 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 109 ms 10668 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 14 ms 1840 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 92 ms 10272 KB Output is correct
10 Correct 6 ms 560 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 107 ms 10712 KB Output is correct
13 Correct 117 ms 14596 KB Output is correct
14 Correct 162 ms 12668 KB Output is correct
15 Correct 156 ms 12956 KB Output is correct
16 Correct 131 ms 14600 KB Output is correct
17 Correct 171 ms 11716 KB Output is correct
18 Correct 185 ms 12632 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 14 ms 1868 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 93 ms 10252 KB Output is correct
10 Correct 5 ms 560 KB Output is correct
11 Correct 6 ms 588 KB Output is correct
12 Correct 105 ms 10756 KB Output is correct
13 Correct 115 ms 14636 KB Output is correct
14 Correct 155 ms 12680 KB Output is correct
15 Correct 161 ms 12960 KB Output is correct
16 Correct 139 ms 14668 KB Output is correct
17 Correct 168 ms 11692 KB Output is correct
18 Correct 196 ms 12632 KB Output is correct
19 Execution timed out 768 ms 71444 KB Time limit exceeded
20 Halted 0 ms 0 KB -