oj.uz

Submission #714403

# Submission time Handle Problem Language Result Execution time Memory
714403 2023-03-24T10:22:03 Z Stickfish Senior Postmen (BOI14_postmen) C++17
100 / 100
 429 ms 45764 KB 
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <cassert>
#include <bitset>
#include <vector>
using namespace std;

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

vector<int> find_euler_cycle() {
    vector<int> ans;
    vector<int> stck = {0};
    while (stck.size()) {
        int v = stck.back();
        if (edg[v].empty()) {
            ans.push_back(v);
            stck.pop_back();
        } else {
            int u = edg[v].back();
            edg[v].pop_back();
            auto it = lower_bound(edg[u].begin(), edg[u].end(), v);
            if (it < edg[u].end() && *it == v) {
                stck.push_back(u);
            }
        }
    }
    return ans;
}

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].push_back(v);
        edg[v].push_back(u);
    }
    for (int i = 0; i < n; ++i)
        sort(edg[i].begin(), edg[i].end());
    vector<int> ans = find_euler_cycle();

    //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 6 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 7 ms 12220 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 9 ms 12192 KB Output is correct
7 Correct 13 ms 12556 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 41 ms 14288 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 8 ms 12176 KB Output is correct
12 Correct 44 ms 14332 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12132 KB Output is correct
2 Correct 6 ms 12124 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 10 ms 12296 KB Output is correct
7 Correct 12 ms 12500 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 40 ms 14296 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 44 ms 14420 KB Output is correct
13 Correct 72 ms 17528 KB Output is correct
14 Correct 57 ms 15824 KB Output is correct
15 Correct 49 ms 15564 KB Output is correct
16 Correct 50 ms 17516 KB Output is correct
17 Correct 67 ms 15536 KB Output is correct
18 Correct 61 ms 15748 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 6 ms 12016 KB Output is correct
3 Correct 7 ms 12100 KB Output is correct
4 Correct 8 ms 12148 KB Output is correct
5 Correct 7 ms 12164 KB Output is correct
6 Correct 11 ms 12244 KB Output is correct
7 Correct 16 ms 12500 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 44 ms 14280 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 8 ms 12168 KB Output is correct
12 Correct 43 ms 14404 KB Output is correct
13 Correct 67 ms 17520 KB Output is correct
14 Correct 56 ms 15924 KB Output is correct
15 Correct 52 ms 15556 KB Output is correct
16 Correct 49 ms 17472 KB Output is correct
17 Correct 76 ms 15556 KB Output is correct
18 Correct 49 ms 15676 KB Output is correct
19 Correct 362 ms 39120 KB Output is correct
20 Correct 373 ms 37824 KB Output is correct
21 Correct 341 ms 33816 KB Output is correct
22 Correct 380 ms 45764 KB Output is correct
23 Correct 219 ms 25364 KB Output is correct
24 Correct 429 ms 35196 KB Output is correct
25 Correct 385 ms 37136 KB Output is correct