Submission #936177

#	Time	Username	Problem	Language	Result	Execution time	Memory
936177		THXuan	Senior Postmen (BOI14_postmen)	C++14	100 / 100	375 ms	65824 KiB

postmen

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;

vector<pair<int,int>>adj[500005];
bool visited[500005];
vector<int>path;
int seen[500005];

void dfs(int s) {
	while (adj[s].size()) {
		int u = adj[s].back().first; int idx = adj[s].back().second;
		adj[s].pop_back();
		if (visited[idx])continue;
		visited[idx] = true;
		dfs(u);
	}
	path.push_back(s);
	seen[s]++;
	if (seen[s] == 2) {
		cout << s << " ";
		path.pop_back();
		while (path.back() != s) {
			cout << path.back() << " ";
			seen[path.back()]--;
			path.pop_back();
		}
		cout << "\n";
		seen[s]--;
	}
}

void solve()
{
	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y; cin >> x >> y;
		adj[x].push_back({ y, i });
		adj[y].push_back({ x, i });
	}
	dfs(1);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

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