Submission #896143

#	Time	Username	Problem	Language	Result	Execution time	Memory
896143		damamila	Senior Postmen (BOI14_postmen)	C++14	0 / 100	1 ms	348 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 << " ";
		}
	}
	//~ cout << "seq " ;
	//~ for (int i : seq) {
		//~ cout << i+1 << " ";
	//~ }
	//~ cout << endl;
	//now make sure no vertices visited multiple times
	map<int, int> index;
	vector<pair<int, int>> groups; //end then start, should have soonest end points first
	for (int i = 0; i < seq.size(); i++) {
		int a = seq[i];
		if (index[a] != 0) { //used before
			groups.push_back({i+1, index[a]});
			index[a] = 0;
		} else {
			index[a] = i+1; //so no confusion if in first position
		}
	}
	int lb = n; //leftmost which has been done
	int rb = 0; //rightmost which has been done
	for (auto x : groups) {
		if (x.second < lb || x.second > rb) { //if no overlap with prev
			for (int i = x.second-1; i < min(x.first-1, lb); i++) {
				cout << seq[i]+1 << " ";
			}
			for (int i = max(rb, min(x.first-1, lb)); i < x.first-1; i++) { //-1 bc so no repetition
				cout << seq[i]+1 << " ";
			}
			cout << endl;
			lb = x.second-1;
			rb = x.first-1;
		}
	}		
	
}

//TL really soon

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:47:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < seq.size(); i++) {
      |                  ~~^~~~~~~~~~~~

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