Submission #904004

#	Time	Username	Problem	Language	Result	Execution time	Memory
904004		damamila	Senior Postmen (BOI14_postmen)	C++14	55 / 100	581 ms	79548 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int n, m;
	cin >> n >> m;
	vector<set<int>> g(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].insert(b);
		g[b].insert(a);
	}
	//dont need to check if possible bc question says is possible
	vector<int> seq;
	stack<int> stak;
	stak.push(0);
	while (!stak.empty()) {
		int u = stak.top();
		//~ cout << u+1 << endl;
		if (g[u].size() > 0) { //if still neighbours
			int v = *g[u].begin();
			stak.push(v);
			g[u].erase(v); //erase edge from both sides
			g[v].erase(u);
		} else { //need to add to tour
			stak.pop();
			seq.push_back(u);
			//~ cout << u+1 << " ";
		}
	}
	
	//now make tours out of this tour
	vector<vector<int>> ans;
	vector<int> count(n, 0);
	stack<int> s; //has verteces which we can remove as appropriate
	for (int i : seq) {
		if (count[i] > 0) {
			ans.push_back({});
			while (s.top() != i) {
				count[s.top()]--;
				ans[ans.size()-1].push_back(s.top());
				s.pop();
			}
			ans[ans.size()-1].push_back(i);
		} else {
			count[i]++;
			s.push(i);
		}
	}
	
	if (s.size() > 1) {
		ans.push_back({});
		while (!s.empty()) {
			ans[ans.size()-1].push_back(s.top());
			s.pop();
		}
	}
		
	for (auto i : ans) {
		for (int j : i) {
			cout << j+1 << " ";
		}
		cout << "\n";
	}
	
}

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