Submission #52980

#	Time	Username	Problem	Language	Result	Execution time	Memory
52980		Bruteforceman	Senior Postmen (BOI14_postmen)	C++11	55 / 100	682 ms	94300 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
#define prev dfsdf
set <int> g[500010];
void addEdge(int p, int q) {
	g[p].insert(q);
	g[q].insert(p);
}
void delEdge(int p, int q) {
	g[p].erase(q);
	g[q].erase(p);
}
vector <int> tour;
void dfs(int x) {
	while (!g[x].empty()){
		int i = *g[x].begin();
		delEdge(x, i);
		dfs(i);
	}
	tour.push_back(x);
}
bool occ[500010];

int main (int argc, char const* argv[])
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		addEdge(p, q);
		assert(p != q);
	}
	dfs(1);
	
	vector <int> cycle;
	for(int i = 0; i < tour.size(); i++) {
		int x = tour[i];
		if(occ[x] == false) {
			cycle.push_back(x);
			occ[x] = true;
		} else {
			while(cycle.back() != x) {
				int node = cycle.back();
				printf("%d ", node);
				occ[node] = false;
				cycle.pop_back();
			}
			printf("%d\n", x);
		}
	}
	return 0;
}
// 1 5 8 7 5 4 7 6 3 4 8 10 9 2 3 1

Compilation message (stderr)

postmen.cpp: In function 'int main(int, const char**)':
postmen.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tour.size(); i++) {
                 ~~^~~~~~~~~~~~~
postmen.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
postmen.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~

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