oj.uz

Submission #714399

# Submission time Handle Problem Language Result Execution time Memory
714399 2023-03-24T10:16:18 Z Stickfish Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 162324 KB 
#include <iostream>
#include <unordered_set>
#include <cassert>
#include <bitset>
#include <vector>
using namespace std;

const int MAXN = 5e5 + 123;
unordered_set<int> edg[MAXN];

void find_euler_cycle(int v, vector<int>& ans) {
    while (edg[v].size()) {
        int u = *edg[v].begin();
        edg[v].erase(u);
        edg[u].erase(v);
        find_euler_cycle(u, ans);
    }
    ans.push_back(v);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[u].insert(v);
        edg[v].insert(u);
    }
    vector<int> ans;
    find_euler_cycle(0, ans);

    //for (auto x : ans)
        //cout << x + 1 << ' ';
    //cout << endl;

    vector<int> stck;
    bitset<MAXN> used;
    for (auto x : ans) {
        vector<int> ccl;
        while (used[x]) {
            used[stck.back()] = 0;
            ccl.push_back(stck.back());
            stck.pop_back();
        }
        if (ccl.size()) {
            for (auto x : ccl)
                cout << x + 1 << ' ';
            cout << '\n';
        }
        stck.push_back(x);
        used[x] = 1;
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27732 KB Output is correct
2 Correct 15 ms 27696 KB Output is correct
3 Correct 14 ms 27732 KB Output is correct
4 Correct 16 ms 28372 KB Output is correct
5 Correct 15 ms 27972 KB Output is correct
6 Correct 17 ms 28500 KB Output is correct
7 Correct 23 ms 30276 KB Output is correct
8 Correct 17 ms 28240 KB Output is correct
9 Correct 88 ms 44060 KB Output is correct
10 Correct 17 ms 28244 KB Output is correct
11 Correct 17 ms 28280 KB Output is correct
12 Correct 104 ms 44252 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 15 ms 27732 KB Output is correct
3 Correct 15 ms 27776 KB Output is correct
4 Correct 17 ms 28460 KB Output is correct
5 Correct 15 ms 27972 KB Output is correct
6 Correct 18 ms 28476 KB Output is correct
7 Correct 24 ms 30292 KB Output is correct
8 Correct 16 ms 28240 KB Output is correct
9 Correct 84 ms 44068 KB Output is correct
10 Correct 18 ms 28312 KB Output is correct
11 Correct 16 ms 28316 KB Output is correct
12 Correct 95 ms 44252 KB Output is correct
13 Correct 126 ms 54664 KB Output is correct
14 Correct 126 ms 47520 KB Output is correct
15 Correct 131 ms 51156 KB Output is correct
16 Correct 125 ms 54664 KB Output is correct
17 Correct 131 ms 43100 KB Output is correct
18 Correct 136 ms 50500 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27732 KB Output is correct
2 Correct 15 ms 27732 KB Output is correct
3 Correct 15 ms 27732 KB Output is correct
4 Correct 16 ms 28560 KB Output is correct
5 Correct 16 ms 27872 KB Output is correct
6 Correct 17 ms 28500 KB Output is correct
7 Correct 25 ms 30324 KB Output is correct
8 Correct 17 ms 28332 KB Output is correct
9 Correct 95 ms 44100 KB Output is correct
10 Correct 16 ms 28320 KB Output is correct
11 Correct 16 ms 28340 KB Output is correct
12 Correct 97 ms 44300 KB Output is correct
13 Correct 124 ms 54676 KB Output is correct
14 Correct 121 ms 47700 KB Output is correct
15 Correct 129 ms 51304 KB Output is correct
16 Correct 121 ms 54616 KB Output is correct
17 Correct 146 ms 43008 KB Output is correct
18 Correct 140 ms 50500 KB Output is correct
19 Execution timed out 624 ms 162324 KB Time limit exceeded
20 Halted 0 ms 0 KB -