oj.uz

답안 #52981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52981 2018-06-27T12:43:58 Z Bruteforceman 어르신 집배원 (BOI14_postmen) C++11
0 / 100
 500 ms 38652 KB 
#include <bits/stdc++.h>
using namespace std;
#define prev dfsdf
unordered_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 = 1; i <= n; i++) {
		g[i].max_load_factor(2048);
		g[i].reserve(0.25);
	}
	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:40: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:34: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
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 27776 KB Output is correct
2 Correct 30 ms 27808 KB Output is correct
3 Correct 26 ms 27776 KB Output is correct
4 Correct 31 ms 28096 KB Output is correct
5 Correct 27 ms 27880 KB Output is correct
6 Correct 31 ms 28160 KB Output is correct
7 Correct 48 ms 29304 KB Output is correct
8 Correct 23 ms 28064 KB Output is correct
9 Execution timed out 1051 ms 38652 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 27656 KB Output is correct
2 Correct 23 ms 27776 KB Output is correct
3 Correct 27 ms 27760 KB Output is correct
4 Correct 32 ms 28160 KB Output is correct
5 Correct 23 ms 27776 KB Output is correct
6 Correct 30 ms 28160 KB Output is correct
7 Correct 47 ms 29304 KB Output is correct
8 Correct 31 ms 28032 KB Output is correct
9 Execution timed out 1080 ms 33912 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 27752 KB Output is correct
2 Correct 24 ms 27776 KB Output is correct
3 Correct 21 ms 27776 KB Output is correct
4 Correct 33 ms 28100 KB Output is correct
5 Correct 29 ms 27776 KB Output is correct
6 Correct 26 ms 28208 KB Output is correct
7 Correct 45 ms 29304 KB Output is correct
8 Correct 22 ms 28032 KB Output is correct
9 Execution timed out 1036 ms 33340 KB Time limit exceeded
10 Halted 0 ms 0 KB -