글 읽기 - 으아아아아아 뭐가 틀린지 안보여서 너무화가납니다아아

alsidnf 4년 전 1

Sparse Table 공부중인 코린이 입니다. 크리스마스에도 방에서 코딩만 하는 저를 살려주세요.ㅠㅠㅠ

#include <cstdio>
#define MAX1 100005
#define MAX2 18
int N, ant[MAX1];
struct Arr {
	int next;
	int len;
}arr[MAX1][MAX2];
struct edge {
	int a, b, len;
}e[MAX1*2];
int num[MAX1];
bool chk[MAX1];
void quick(int left, int right)//퀵정렬
{
	int l = left - 1, r = right + 1, m = e[(left + right) / 2].a;
	edge temp;
	if (left < right)
	{
		while (1)
		{
			while (e[++l].a < m);
			while (e[--r].a > m);
			if (l >= r) break;
			temp = e[l]; e[l] = e[r]; e[r] = temp;
		}
		quick(left, l - 1);
		quick(r + 1, right);
	}
}
void dfs(int n)//1을 기준으로 위에있는 집을 찾습니다.
{
	chk[n] = 1;
	for (int i = num[n - 1]; i < num[n]; i++)
	{
		if (chk[e[i].b]) continue;
		arr[e[i].b][0].next = n;
		arr[e[i].b][0].len = e[i].len;
		dfs(e[i].b);
	}
}
int main()
{
	scanf("%d", &N);
	for(int i=1;i<=N;i++) scanf("%d", &ant[i]);
	for (int i = 0; i < N-1; i++)
	{
		scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].len);
		e[i + N - 1].a = e[i].b;
		e[i + N - 1].b = e[i].a;
		e[i + N - 1].len = e[i].len;
		num[e[i].a]++;
		num[e[i].b]++;
	}
	for (int i = 1; i <= N; i++) num[i] += num[i - 1];

	quick(0, N * 2 - 3);
	dfs(1);
	//배열에 arr[i][j] 는 i에서 2^j만큼 이동했을때 도착하는곳(next)와 길이(len)입니다
	for (int i = 1; i < MAX2; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			arr[j][i].next = arr[arr[j][i - 1].next][i - 1].next;
			arr[j][i].len = arr[j][i - 1].len + arr[arr[j][i - 1].next][i - 1].len;
		}
	}
	//en은 남은에너지 x는 현재위치 입니다.
	int en, x;
	for (int n = 1; n <= N; n++)
	{
		en = ant[n];
		x = n;
		for (int i = MAX2 - 1; (i >= 0) && en; i--)
		{
			if (en >= arr[x][i].len && arr[x][i].next != 0)
			{
				x = arr[x][i].next;
				en -= arr[x][i].len;
			}
			if (x == 1) break;
		}
		printf("%d\n", x);
	}
}

alsidnf 4년 전 0

해결됬습니다 ㅠㅠ 78번79번 위치가 반대라서 x가 바뀌고 en에서 빼줘서 값이 다르게 되었네요 ㅠㅠㅠ 클스마스에도 다들 즐거운ㅇ 코딩하세요 ㅋㅋ!!...

panda959595 4년 전 1

저도 왜 틀렸는지 고민하다가 질문글 찾아봤는데 저랑 똑같은 부분이었네요ㅋㅋㅋ

덕분에 해결했습니다. 감사합니다.

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

문제

문제

출처

ICPC

으아아아아아 뭐가 틀린지 안보여서 너무화가납니다아아

alsidnf 4년 전 1

alsidnf 4년 전 0

panda959595 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말