Submission #52984

#	Time	Username	Problem	Language	Result	Execution time	Memory
52984		Bruteforceman	Senior Postmen (BOI14_postmen)	C++11	55 / 100	651 ms	55776 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
#define prev dfsdf
vector <int> g[500010];
int l[500010], r[500010];
bool del[500010];
vector <int> tour;

void dfs(int x) {
	while (!g[x].empty()){
		int i = g[x].back();
		g[x].pop_back();
		if(del[i]) continue;
		del[i] = true;
		int y = l[i] ^ r[i] ^ x;
		dfs(y);
	}
	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);
		l[i] = p;
		r[i] = q;
		g[p].push_back(i);
		g[q].push_back(i);
	}
	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:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tour.size(); i++) {
                 ~~^~~~~~~~~~~~~
postmen.cpp:25: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:28: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