Submission #212372

#	Time	Username	Problem	Language	Result	Execution time	Memory
212372		dolphingarlic	Senior Postmen (BOI14_postmen)	C++14	100 / 100	461 ms	47224 KiB

postmen

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
using namespace std;
 
vector<pair<int, int>> g[500001];
bool v[500001], u[500001];
int nxt[500001];
 
void dfs(int node) {
	if (v[node]) {
		while (v[node]) {
			v[node] = false;
			cout << node << ' ';
			node = nxt[node];
		}
		cout << '\n';
	}
	while (g[node].size()) {
		int c, idx;
		tie(c, idx) = g[node].back();
		g[node].pop_back();
		if (!u[idx]) {
			u[idx] = true;
			v[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;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	
	dfs(1);
	return 0;
}

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