Submission #714403

#	Time	Username	Problem	Language	Result	Execution time	Memory
714403		Stickfish	Senior Postmen (BOI14_postmen)	C++17	100 / 100	429 ms	45764 KiB

postmen

#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 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45