Submission #1104193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104193		VectorLi	Senior Postmen (BOI14_postmen)	C++14	100 / 100	315 ms	67256 KiB

postmen

#include <bits/stdc++.h>
#define long long long

using namespace std;

const int V = (int) 5E5;
const int E = (int) 5E5;

int n, m;
vector<pair<int, int>> e[V];

int t[E];
int c[V];
vector<int> a;

void DFS(int u) {
	while (e[u].empty() == 0) {
		int v, i;
		tie(v, i) = e[u].back();
		e[u].pop_back();
		if (t[i] == 0) {
			t[i] = 1;
			DFS(v);
		}
	}
	a.push_back(u);
	c[u] = c[u] + 1;
	if (c[u] > 1) {
		cout << u + 1 << " ";
		c[u] = c[u] - 1;
		a.pop_back();
		while (a.back() != u) {
			cout << a.back() + 1 << " ";
			c[a.back()] = c[a.back()] - 1;
			a.pop_back();
		}
		cout << "\n";
	}
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u = u - 1, v = v - 1;
		e[u].push_back({v, i});
		e[v].push_back({u, i});
	}
	DFS(0);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	int t;
	t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

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