Submission #1247726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247726		pasta	Senior Postmen (BOI14_postmen)	C++20	100 / 100	335 ms	78784 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define pb	push_back
#define F   first
#define S   second
#define int long long
const int maxn = 1e6 + 10;
const int LOG = 21;
const int mod = 1e9 + 7;

int n, m;
vector<pii> G[maxn];
vector<int> path, tour;
bool mark[maxn];
int vis[maxn];

void Tour(int v) {
	while (!G[v].empty()) {
		auto [u, id] = G[v].back();
		G[v].pop_back();
		if (mark[id]) continue;
		mark[id] = 1;
		Tour(u);
	}
	path.pb(v);
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int v, u;
		cin >> v >> u;
		G[v].pb({u, i});
		G[u].pb({v, i});
	}
	
	Tour(1);
	
	for (int v : path) {
		if (vis[v]) {
			while (tour.back() != v) {
				cout << tour.back() << ' ';
				vis[tour.back()]--;
				tour.pop_back();
			}
			cout << v << '\n';
		}
		else {
			tour.pb(v);
			vis[v]++;
		}
	}
}

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