oj.uz

Submission #896115

# Submission time Handle Problem Language Result Execution time Memory
896115 2023-12-31T20:17:20 Z damamila Senior Postmen (BOI14_postmen) C++14
0 / 100
 500 ms 348 KB 
#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>> graph(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		graph[a].insert(b);
		graph[b].insert(a);
	}
	//dont need to check if possible bc question says is possible
	for (int i = 0; i < n; i++) { //for every vertex
		while (graph[i].size() > 0) { //whilst tours can start from here
			vector<set<int>> g = graph; //so not remove all edges forever
			vector<int> seq;
			stack<int> stak;
			stak.push(i);
			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
			auto it = seq.begin()+1;
			vector<int> ans;
			ans.push_back(seq[0]);
			while (it < seq.end()) {
				//~ cout << *it+1;
				ans.push_back(*it);
				auto next = find(it+1, seq.end(), *it);
				while (next < seq.end()) { //if this knot occurs again
					it = next;
					auto next = find(it+1, seq.end(), *it);
					//~ cout << " " << *it+1;
				}
				//~ cout << endl;
				it++;
			}
			int prev = -1;
			//~ cout << endl;
			for (int x : ans) {
				if (prev != -1) { //removal of edges used
					graph[prev].erase(x);
					graph[x].erase(prev);
				}
				prev = x;
			}
			for (int x = 1; x < ans.size(); x++) {
				cout << ans[x]+1 << " ";
			}
			cout << endl;
		}		
	}
}

//ES GIBT KEINE MOEGLICHEN EULER TOUREN< WARUMMMMMMM

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:57:11: warning: variable 'next' set but not used [-Wunused-but-set-variable]
   57 |      auto next = find(it+1, seq.end(), *it);
      |           ^~~~
postmen.cpp:72:22: 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]
   72 |    for (int x = 1; x < ans.size(); x++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1054 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1048 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1083 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -