제출 #1309948

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309948		888313666	어르신 집배원 (BOI14_postmen)	C++20	55 / 100	631 ms	111968 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<set<int>> adj;
vector<int> et, x;
stack<int> s;

void dfs(const int u) {
    while (!adj[u].empty()) {
        const auto v=*adj[u].begin();
        adj[u].erase(v);
        adj[v].erase(u);
        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].insert(--b);
        adj[b].insert(a);
    }
    et.reserve(m+5);
    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