oj.uz

Submission #714395

# Submission time Handle Problem Language Result Execution time Memory
714395 2023-03-24T10:14:55 Z Stickfish Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 169060 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() {
    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 19 ms 27732 KB Output is correct
2 Correct 17 ms 27712 KB Output is correct
3 Correct 17 ms 27748 KB Output is correct
4 Correct 18 ms 28472 KB Output is correct
5 Correct 16 ms 27852 KB Output is correct
6 Correct 18 ms 28504 KB Output is correct
7 Correct 27 ms 30420 KB Output is correct
8 Correct 17 ms 28244 KB Output is correct
9 Correct 128 ms 44732 KB Output is correct
10 Correct 19 ms 28260 KB Output is correct
11 Correct 17 ms 28244 KB Output is correct
12 Correct 160 ms 45120 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27664 KB Output is correct
2 Correct 15 ms 27732 KB Output is correct
3 Correct 19 ms 27700 KB Output is correct
4 Correct 19 ms 28472 KB Output is correct
5 Correct 16 ms 27860 KB Output is correct
6 Correct 23 ms 28532 KB Output is correct
7 Correct 27 ms 30420 KB Output is correct
8 Correct 17 ms 28292 KB Output is correct
9 Correct 124 ms 44756 KB Output is correct
10 Correct 22 ms 28272 KB Output is correct
11 Correct 19 ms 28244 KB Output is correct
12 Correct 147 ms 45112 KB Output is correct
13 Correct 183 ms 55812 KB Output is correct
14 Correct 194 ms 48780 KB Output is correct
15 Correct 179 ms 52104 KB Output is correct
16 Correct 169 ms 55728 KB Output is correct
17 Correct 178 ms 44320 KB Output is correct
18 Correct 182 ms 51408 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 16 ms 27732 KB Output is correct
3 Correct 16 ms 27732 KB Output is correct
4 Correct 19 ms 28408 KB Output is correct
5 Correct 16 ms 27952 KB Output is correct
6 Correct 19 ms 28464 KB Output is correct
7 Correct 28 ms 30448 KB Output is correct
8 Correct 18 ms 28244 KB Output is correct
9 Correct 120 ms 44724 KB Output is correct
10 Correct 18 ms 28288 KB Output is correct
11 Correct 17 ms 28284 KB Output is correct
12 Correct 130 ms 45152 KB Output is correct
13 Correct 182 ms 55812 KB Output is correct
14 Correct 191 ms 48752 KB Output is correct
15 Correct 169 ms 52060 KB Output is correct
16 Correct 173 ms 55736 KB Output is correct
17 Correct 185 ms 44124 KB Output is correct
18 Correct 179 ms 51604 KB Output is correct
19 Execution timed out 875 ms 169060 KB Time limit exceeded
20 Halted 0 ms 0 KB -