Submission #31508

#	Time	Username	Problem	Language	Result	Execution time	Memory
31508		minkank	Senior Postmen (BOI14_postmen)	C++14	55 / 100	1091 ms	113380 KiB

postmen

#include <iostream>
#include <set>
#include <stack>
using namespace std;

const int N = 5e5 + 5;
int n, m;
set<int> s[N];
multiset<int> ss;
stack<int> st;

void dfs(int u) {
	while(s[u].size()) {
		int v = *s[u].begin();
		s[u].erase(v); s[v].erase(u);
		dfs(v);
	}
	if(ss.find(u) != ss.end()) {
		while(st.top() != u) {
			cout << st.top() << ' '; 
			multiset<int>::iterator it = ss.find(st.top());
			ss.erase(it);
			st.pop();
		}
		cout << u;
		multiset<int>::iterator it = ss.find(st.top());
		ss.erase(it);
		st.pop();
		cout << endl;
	}
	st.push(u); ss.insert(u);
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		s[u].insert(v); s[v].insert(u);
	}
	dfs(1);
}

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