Submission #1326766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326766		i_am_blindfold	Senior Postmen (BOI14_postmen)	C++20	100 / 100	322 ms	72460 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

vector<pair<int, int>> adj[N];
vector<int> vis(N, 0);
vector<int> lst(N, - 1);
vector<int> path;

void dfs(int u) {
    while (!adj[u].empty()) {
        auto [v, i] = adj[u].back();
        adj[u].pop_back();
        if (vis[i]) continue;
        vis[i] = 1;
        dfs(v);
    }
    path.push_back(u);
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }

    dfs(1);

    reverse(path.begin(), path.end());
    vector<int> cur;
    for (int i = 0; i < (int)path.size(); i++) {
        if (lst[path[i]] == - 1) {
            cur.push_back(path[i]);
            lst[path[i]] = 1;
        } else {
            vector<int> op;
            while (cur.back() != path[i]) {
                op.push_back(cur.back());
                lst[cur.back()] = - 1;
                cur.pop_back();
            }
            op.push_back(path[i]);
            reverse(op.begin(), op.end());
            for (int &j: op) {
                cout << j << ' ';
            }
            cout << '\n';
        }
    }

    return 0;
}

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45