글 읽기 - 민식우선탐색 데이터 추가가 필요할 것 같습니다

topology 7년 전 2

저는 이 문제를 각 노드를 방문할 때마다 그 이웃 노드의 중간값의 위치를 좌우로 적절히 움직여서 업데이트해주는 방식으로 코딩해서 accept 받았지만, 이는 worst case O(V^2)의 시간복잡도를 가져서 틀린 풀이입니다.

그래서 아래와 같은 데이터를 돌리면 시간초과가 납니다. 데이터를 추가하면 좋을 것 같습니다.

#include <stdio.h>

const int V = 100000;
const int E = 1000000;

int main()
{
	//freopen("test.txt", "w", stdout);
	int mx = 99999;
	printf("%d %d\n", mx, 2*mx-3);
	int e = 2*mx-3;
	for (int i=2; i<=mx; i++){
		printf("%d %d\n", 1, i);
		e --;
	}
	e --;
	printf("2 %d\n", 1+((mx+1)>>1));
	int st = (mx+1)>>1;
	int sign = 1;
	int d = 1;
	while (e--){
		printf("%d %d\n", st+1, st+sign*d+1);
		st += sign*d;
		d ++;
		sign = -sign;
	}
	return 0;
}

baekjoon 7년 전 1

https://www.acmicpc.net/rejudg...

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

문제

문제

출처

ICPC

민식우선탐색 데이터 추가가 필요할 것 같습니다

topology 7년 전 2

baekjoon 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말