Submission #130408

# Submission time Handle Problem Language Result Execution time Memory
130408 2019-07-15T06:58:32 Z 임유진(#3151) Information (CEOI08_information) C++14
0 / 100
2 ms 504 KB
#include <stdio.h>
#include <vector>

using namespace std;

#define MAXM 30
#define fi first
#define se second

typedef pair<int, int> pii;

int A[MAXM], B[MAXM];
vector<pii> ed[2][MAXM];
vector<int> ans[2];
bool chk[2][MAXM];

void dfs(int k, int x) {
	//printf("dfs(k = %d, x = %d)\n", k, x);
	chk[k][x] = true;
	for(auto a : ed[k][x]) if(!chk[k][a.fi]){
		dfs(k, a.fi);
		ans[k].push_back(a.se);
	}
}

int main() {
	int N, M;

	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; i++) scanf("%d%d", A + i, B + i);

	for(int i = 0; i < (1 << M); i++) {
		for(int j = 1; j <= N; j++) {
			ed[0][j].clear();
			ed[1][j].clear();
			chk[0][j] = chk[1][j] = false;
		}
		ans[0].clear();
		ans[1].clear();

		int cnt[2]={0, 0};
		for(int j = 0; j < M; j++) {
			ed[(i >> j) & 1][A[j]].push_back(make_pair(B[j], j + 1));
			ed[(i >> j) & 1][B[j]].push_back(make_pair(A[j], j + 1));
			cnt[(i >> j) & 1]++;
		}
		if(cnt[0] < N - 1 || cnt[1] < N - 1) continue;

		//printf("i = %d\n", i);
		dfs(0, 1);
		dfs(1, 1);
		bool b = true;
		for(int j = 1; j <= N; j++) if(!chk[0][j] || !chk[1][j]) b = false;
		if(b) {
			for(auto a : ans[0]) printf("%d ", a);
			printf("\n");
			for(auto a : ans[1]) printf("%d ", a);
			return 0;
		}
	}
	printf("NONE");
	return 0;
}

Compilation message

information.cpp: In function 'int main()':
information.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
information.cpp:30:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < M; i++) scanf("%d%d", A + i, B + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 376 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 376 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 256 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -