제출 #1184132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184132		qrn	Senior Postmen (BOI14_postmen)	C++20	55 / 100	195 ms	41328 KiB

postmen

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

#define SPEED ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mxN = 2e5 + 5;
const intt inf = 1e18;
const intt mod = 1e9 + 7;

vector<vector<pair<intt,intt>>> graph;
vector<intt> usedE(mxN), usedN(mxN);
vector<intt> path;
vector<vector<intt>> ans;

void dfs(intt node) {
    if(usedN[node]) { 
        vector<intt> pushla;
        while(not path.empty() && path.back() != node) {
            usedN[path.back()] = 0;
            pushla.pb(path.back());
            path.pop_back();
        } 
        pushla.pb(node);
        ans.pb(pushla);
    } else {
        usedN[node] = 1;
        path.pb(node);
    }
    intt f = 0;
    if(graph[node].empty()) {
        return;
    }
    while(usedE[graph[node].back().se]) {
        graph[node].pop_back();
        if(graph[node].empty()) {
            f = 1; break;
        }
    }
    if(f) return;
    usedE[graph[node].back().se] = 1;
    dfs(graph[node].back().fi);
}

void solve() {
    intt N, M;
    cin >> N >> M;

    graph.assign(N + 1, vector<pair<intt,intt>>{});
    for(intt i = 0; i < M; i++) {
        intt a, b;
        cin >> a >> b;
        graph[a].pb({b,i});
        graph[b].pb({a,i});
    }
    for(intt i = 1; i <= N; i++) {
        if(!graph[i].empty()) dfs(i);
    }

    for(vector<intt> &P : ans) {
        for(intt i : P) cout << i << " ";
        cout << endl;
    }//edu
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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