Submission #1309469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309469		Balsa	Senior Postmen (BOI14_postmen)	C++20	100 / 100	349 ms	96868 KiB

postmen

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

#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using ll = long long;
const ll MAXN = 500005, MAXM = 500005;

vector<pair<ll, ll>> edges[MAXN];
bool vis[MAXM];
vector<ll> path;
ll st[MAXN];

void dfs(ll v) {
    while (!edges[v].empty()) {
        auto[u, id] = edges[v].back();
        edges[v].pop_back();
        if (vis[id]) continue;
        vis[id] = 1;
        dfs(u);
    }

    path.push_back(v);
    st[v]++;

    if (st[v] == 2) {
        st[v]--;
        path.pop_back();
        cout << v+1 << ' ';
        while (path.back() != v) {
            cout << path.back()+1 << ' ';
            st[path.back()]--;
            path.pop_back();
        }
        cout << '\n';
    }
}

void solve() {
    ll n, m;
    cin >> n >> m;
    for (ll i = 0; i < m; i++) {
        ll v, u;
        cin >> v >> u;
        v--, u--;
        edges[v].push_back({u, i});
        edges[u].push_back({v, i});
    }

    dfs(0);

    // for (ll x : path) cout << x+1 << ' ';
    // cout << '\n';
}

int main() {
    // freopen("promote.in", "r", stdin);
    // freopen("promote.out", "w", stdout);
 
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

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