Submission #535907

#	Time	Username	Problem	Language	Result	Execution time	Memory
535907		sliviu	Senior Postmen (BOI14_postmen)	C++17	0 / 100	260 ms	262144 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, m, x, y;
	cin >> n >> m;
	vector<vector<pair<int, int>>> G(n + 1);
	vector<int> seen(m);
	for (int i = 0; i < m; ++i) {
		cin >> x >> y;
		G[x].emplace_back(y, i);
		G[y].emplace_back(x, i);
	}
	vector<int> ans, cur;
	cur.reserve(n + 1);
	cur.emplace_back(1);
	while (!cur.empty()) {
		int top = cur.back();
		if (G[top].empty()) {
			ans.emplace_back(top);
			cur.back();
		}
		else {
			if (seen[G[top].back().second]) {
				G[top].pop_back();
				continue;
			}
			auto [node, e] = G[top].back();
			cur.emplace_back(node);
			seen[e] = 1;
			G[top].pop_back();
		}
	}
	seen.assign(n + 1, 0);
	for (auto x : ans)
		if (!seen[x]) {
			seen[x] = 1;
			cur.emplace_back(x);
		}
		else {
			cout << x << ' ';
			while (cur.back() != x) {
				cout << cur.back() << ' ';
				seen[cur.back()] = 0;
				cur.pop_back();
			}
			cout << '\n';
		}
}

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