Submission #535906

#	Time	Username	Problem	Language	Result	Execution time	Memory
535906		sliviu	Senior Postmen (BOI14_postmen)	C++17	55 / 100	647 ms	43724 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);
	}
	stack<int> cur;
	cur.emplace(1);
	vector<int> ans;
	while (!cur.empty()) {
		int top = cur.top();
		if (G[top].empty()) {
			ans.emplace_back(top);
			cur.pop();
		}
		else {
			if (seen[G[top].back().second]) {
				G[top].pop_back();
				continue;
			}
			auto [node, e] = G[top].back();
			cur.emplace(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(x);
		}
		else {
			cout << x << ' ';
			while (cur.top() != x) {
				cout << cur.top() << ' ';
				seen[cur.top()] = 0;
				cur.pop();
			}
			cout << '\n';
		}
}

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