Submission #1309960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309960		888313666	Senior Postmen (BOI14_postmen)	C++20	55 / 100	556 ms	78152 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ <<' '<<
#define print(x) cout<<#x<<": "<<(x)<<endl
#define vrint(v) for (const auto &e:(v)) cout<<e+1<<' '; cout<<'\n';

vector<vector<array<int, 2>>> adj;
vector<int> et, x, vis;
stack<int> s;

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    adj.resize(n);
    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});

    }
    et.reserve(m+5);
    vis.assign(m, 0);
    dfs(0);
    reverse(et.begin(), et.end());
    et.push_back(0);
    x.resize(n, 0);
    //vrint(et);
    for (const auto e:et) {
        if (x[e]) {
            int v;
            do {
                v=s.top();
                s.pop();
                x[v]=0;
                cout<<v+1<<' '<<flush;
            } while (v!=e);
            s.push(e);
            x[e]=1;
            cout<<'\n';
        } else {
            s.push(e);
            x[e]=1;
        }
    }
}

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