Submission #211568

#	Time	Username	Problem	Language	Result	Execution time	Memory
211568		admin	Senior Postmen (BOI14_postmen)	C++14	100 / 100	462 ms	57592 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
 
vector<pair<int, int>> graph[500001];
bool visited[500001], used[500001];
int nxt[500001];
 
void dfs(int node) {
	if (visited[node]) {
		while (visited[node]) {
			visited[node] = false;
			cout << node << ' ';
			node = nxt[node];
		}
		cout << '\n';
	}
	while (graph[node].size()) {
		int c, idx;
		tie(c, idx) = graph[node].back();
		graph[node].pop_back();
		if (!used[idx]) {
			used[idx] = true;
			visited[node] = true;
			nxt[node] = c;
			dfs(c);
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back({b, i});
		graph[b].push_back({a, i});
	}
	
	dfs(1);
	return 0;
}

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