Submission #1172113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172113		Pekiban	Senior Postmen (BOI14_postmen)	C++20	100 / 100	219 ms	63660 KiB

postmen

#include <bits/stdc++.h>

using namespace std;
#define pb push_back

const int N = 5e5 + 5;
vector<array<int, 2>> g[N];
vector<int> e;
bool vis[N], vis2[N];
void dfs(int s) {
    vis2[s] = 1;
    while (!g[s].empty()) {
        auto [u, w] = g[s].back();  g[s].pop_back();
        if (vis[w]) continue;
        vis[w] = 1;
        dfs(u);
    }
    e.pb(s);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb({v, i}); g[v].pb({u, i});
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis2[i])   dfs(i);
    }
    vector<vector<int>> ans;
    int f[n+1];
    fill(f, f+n+1, 0);
    stack<int> z;
    for (int i = 0; i < e.size(); ++i) {
        bool ok = 1;
        if (f[e[i]]) {
            ans.pb({e[i]});
            while (z.top() != e[i]) {
                ans.back().pb(z.top());
                f[z.top()] = 0;
                z.pop();
            }
            z.pop();
            ok = 0;
        }
        z.push(e[i]), f[e[i]] = 1;
    }
    for (auto x : ans) {
        for (auto y : x) {
            cout << y << ' ';
        }
        cout << '\n';
    }
}

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