Submission #1184134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184134		qrn	Senior Postmen (BOI14_postmen)	C++20	0 / 100	2 ms	3396 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(intt i = 0; i < ans.size(); i++) {
        for(intt j = 0; j < ans[i].size(); j++){
            cout << ans[i][j] << " "[j == ans[i].size() - 1];
        }
        cout << endl[i == ans.size()-1];
    }
}

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

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