oj.uz

Submission #52980

# Submission time Handle Problem Language Result Execution time Memory
52980 2018-06-27T12:42:08 Z Bruteforceman Senior Postmen (BOI14_postmen) C++11
55 / 100
 500 ms 94300 KB 
#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

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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 20 ms 24192 KB Output is correct
5 Correct 23 ms 23936 KB Output is correct
6 Correct 26 ms 24448 KB Output is correct
7 Correct 37 ms 25848 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 175 ms 37792 KB Output is correct
10 Correct 21 ms 24192 KB Output is correct
11 Correct 21 ms 24064 KB Output is correct
12 Correct 174 ms 37880 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 20 ms 23776 KB Output is correct
3 Correct 20 ms 23808 KB Output is correct
4 Correct 23 ms 24192 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 21 ms 24448 KB Output is correct
7 Correct 40 ms 25984 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 230 ms 37888 KB Output is correct
10 Correct 21 ms 24192 KB Output is correct
11 Correct 20 ms 24064 KB Output is correct
12 Correct 185 ms 37876 KB Output is correct
13 Correct 122 ms 37880 KB Output is correct
14 Correct 140 ms 37880 KB Output is correct
15 Correct 155 ms 37880 KB Output is correct
16 Correct 126 ms 37856 KB Output is correct
17 Correct 160 ms 37880 KB Output is correct
18 Correct 144 ms 35108 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 28 ms 24192 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 25 ms 24424 KB Output is correct
7 Correct 33 ms 25848 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 202 ms 37856 KB Output is correct
10 Correct 21 ms 24168 KB Output is correct
11 Correct 20 ms 24064 KB Output is correct
12 Correct 193 ms 37832 KB Output is correct
13 Correct 122 ms 37856 KB Output is correct
14 Correct 163 ms 37936 KB Output is correct
15 Correct 174 ms 37864 KB Output is correct
16 Correct 151 ms 37880 KB Output is correct
17 Correct 159 ms 37880 KB Output is correct
18 Correct 164 ms 35060 KB Output is correct
19 Execution timed out 682 ms 94300 KB Time limit exceeded
20 Halted 0 ms 0 KB -