Submission #555009

#	Time	Username	Problem	Language	Result	Execution time	Memory
555009		sidon	Senior Postmen (BOI14_postmen)	C++17	100 / 100	377 ms	65772 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
 
const int Z = 5e5;
 
int N, M;
vector<array<int, 2>> g[Z];
vector<int> o, s;
bool vis[Z];
 
void dfs(int u) {
	while(!empty(g[u])) {
		auto [v, i] = g[u].back();
		g[u].pop_back();
		if(!vis[i]) vis[i] = 1, dfs(v);
	}
	o.push_back(u);
}
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
 
	while(M--) {
		int u, v; cin >> u >> v;
		--u, --v;
		g[u].push_back({v, M});
		g[v].push_back({u, M});
	}
 
	dfs(0);
 
	fill(vis, vis + N, 0);

	for(int u : o) {
		if(vis[u]) {
			for(int v = -1; u != v; s.pop_back()) {
				vis[v = s.back()] = 0;
				cout << v + 1 << ' ';
			}
			cout << '\n';
		}
		s.push_back(u);
		vis[u] = 1;
	}
}

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