글 읽기 - 70%에서 틀립니다 ㅜ 반례가 있을까요

dongbin97 3년 전 1

입력받는 bfs순서대로 읽어가면서 현재위치에서 확인해야 하는 자식들이 제 위치에 있는지 판단하도록 구현했는데

중간에 틀린다고 하네요

혹시 반례가 보이시면 얘기해주세요 ㅜㅜ

#include <iostream>
#include <vector>
#define SIZE 100001
using namespace std;

vector<int> a[SIZE];
bool check[SIZE];
int num[SIZE], N, start[SIZE];

int bfs() {
	int i, j, k, flag;
	for (i = 0; i < N-1; i++) {
		int x = num[i];
		for (j = start[i]; j < start[i + 1]; j++) {
			flag = 0;
			for (k = 0; k < a[x].size(); k++) {
				if (check[a[x][k]] == false) {
					if (num[j] == a[x][k]) {
						check[a[x][k]] = true;
						flag = 1;
					}
				}
			}
			if (flag == 0) {
				return 0;
			}
		}
	}
	return 1;
}
int main() {
	int n1, n2,i,j;
	scanf("%d", &N);
	for (i = 0; i < N - 1; i++) {
		scanf("%d %d", &n1, &n2);
		a[n1].push_back(n2);
		a[n2].push_back(n1);
	}
	for (i = 0; i < N; i++)
		scanf("%d", &num[i]);

	start[0] = 1;
	check[num[0]] = 1;
	for (i = 1; i < N; i++) {
		start[i] = start[i - 1];
		for (j = 0; j < a[num[i - 1]].size(); j++) {
			if (check[a[num[i - 1]][j]] == false) {
				check[a[num[i - 1]][j]] = true;
				start[i]++;
			}
		}
	}

	for (i = 0; i <= N; i++)
		check[i] = false;

	printf("%d\n", bfs());
	return 0;
}

dongbin97 3년 전 2

자답입니다

bfs시작을 1로 한다는 이야기를 항상 1로 시작하게 테스트 케이스로 넣어 채점한다고 해석했는데

시작이 1이 아닌 케이스는 예외처리 해주어야합니다

여러분은 이런 걸로 시간 오래 끌지 마시길....

huh0918 2년 전 0

혹시 예외처리라는게 정확히 어떤 걸 말씀하시는지 알수 있을까요? 저도 비슷한 상황인것 같아서..

1이 첫입력이 아니라면 틀린걸로 판단하고 0을 출력하라는 말씀이신가요 아니면 1이 아니어도 맞는 입력으로 간주하고 알고리즘을 수행해야 한다는 뜻인가요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

70%에서 틀립니다 ㅜ 반례가 있을까요

dongbin97 3년 전 1

dongbin97 3년 전 2

huh0918 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말