Submission #1241853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241853		pedroslrey	Senior Postmen (BOI14_postmen)	C++20	100 / 100	358 ms	70592 KiB

postmen

#include <bits/stdc++.h>

using namespace std;
using graph = vector<vector<pair<int, int>>>;

int main() {
	int n, m;
	cin >> n >> m;

	graph G(n);
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;

		--u; --v;

		G[u].emplace_back(v, i);
		G[v].emplace_back(u, i);
	}

	vector<int> used(m);
	vector<int> order;
	function<void (int)> dfs = [&](int u) {
		while (!G[u].empty()) {
			auto [v, i] = G[u].back();
			G[u].pop_back();

			if (!used[i]) {
				used[i] = true;
				dfs(v);
			}
		}

		order.push_back(u);
	};

	dfs(0);

	vector<bool> marc(n);
	vector<vector<int>> cycles;

	stack<int> st;
	for (int x: order) {
		if (marc[x]) {
			cycles.emplace_back(1, x);
			while (st.top() != x) {
				marc[st.top()] = false;
				cycles.back().push_back(st.top());
				st.pop();
			}
			st.pop();
		}

		marc[x] = true;
		st.push(x);
	}

	for (vector<int> &xs: cycles) {
		for (int x: xs)
			cout << x + 1 << " ";
		cout << "\n";
	}
}

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