글 읽기 - 반례 부탁드립니다.

ric5 3년 전 0

1 2 1

1 3 2

2 4 3

2 5 4

3 6 5

3 7 6

4 8 7

4 9 8

5 10 9

5 11 10

6 12 11

6 13 12

7 14 13

7 15 14

이렇게 트리를 만든뒤 넣어봐도 답은 잘 나오는데 제출하면 틀렸다고 뜹니다. 오류가 있을까요??

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define INF 1000001
using namespace std;

int N, K;
int max_H;

vector<pair<int, int> > input[100001];
int tree[100001][20][3];// tree[i][h][0] 에는 h번째 위의 노드 번호, [1]에는 max값, [2]에는 min값
int depth[100001];

void make_tree(int me, int parent, int val)
{
	depth[me] = depth[parent] + 1;
	tree[me][0][0] = parent;
	tree[me][0][1] = val;
	tree[me][0][2] = val;

	for (int i = 1; i <= max_H; i++)
	{

		int temp = tree[me][i - 1][0];
		tree[me][i][0] = tree[temp][i - 1][0];
		tree[me][i][1] = 0;
		tree[me][i][2] = INF;
	}

	int s = input[me].size();
	for (int i = 0; i < s; i++)
	{
		int next = input[me][i].first;
		int l = input[me][i].second;
		if (next != parent)
			make_tree(next, me, l);
	}
}

void define_max_min()
{
	for (int i = 1; i <= max_H; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int temp = tree[j][i - 1][0];
			tree[j][i][1] = max(tree[j][i - 1][1], tree[temp][i - 1][1]);
			tree[j][i][2] = min(tree[j][i - 1][2], tree[temp][i - 1][2]);
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	int a, b, c;
	max_H = (int)ceil(log2(100001) + 1);
	cin >> N;
	for (int i = 0; i < N - 1; i++)
	{
		cin >> a >> b >> c;
		input[a].push_back(make_pair(b, c));
		input[b].push_back(make_pair(a, c));
	}
	depth[0] = -1;
	make_tree(1, 0, 0);
	define_max_min();

	cin >> K;
	while (K--)
	{
		cin >> a >> b;

		int answer1 = 0;
		int answer2 = INF;
		if (depth[a] != b)
		{
			if (depth[a] > depth[b])
			{
				int temp = a;
				a = b;
				b = temp;
			}

			for (int i = max_H; i >= 0; i--)
			{
				if (depth[tree[b][i][0]] >= depth[a])
				{
					answer1 = max(answer1, tree[b][i][1]);
					answer2 = min(answer2, tree[b][i][2]);
					b = tree[b][i][0];
				}
			}
		}

		if (a != b)
		{
			for (int i = max_H; i >= 0; i--)
			{
				if (tree[a][i][0] != tree[b][i][0] && tree[a][i][0] != 0 && tree[b][i][0] != 0)
				{
					answer1 = max({ answer1 , tree[a][i][1] , tree[b][i][1] });
					answer2 = min({ answer2 , tree[a][i][2] , tree[b][i][2] });
					a = tree[a][i][0];
					b = tree[b][i][0];
				}
			}
			answer1 = max({ answer1 , tree[a][0][1] , tree[b][0][1] });
			answer2 = min({ answer2 , tree[a][0][2] , tree[b][0][2] });
		}

		printf("%d %d\n", answer2, answer1);
	}

	return 0;



}

yj10516 3년 전 1

잘 짜신것 같은데 79번째줄에 실수가 있는것 같아요

79번째 줄에 if(depth[a] != depth[b]) 를 의도하지 않으셨나요?

ric5 3년 전 1

감사합니다 해결할 수 있었습니다!!

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

문제

문제

출처

ICPC

반례 부탁드립니다.

ric5 3년 전 0

yj10516 3년 전 1

ric5 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말