글 읽기 - 3176 도로네트워크 왜틀렸을까요 ㅜㅜ

kally613 3년 전 1

3176 도로네트워크 왜틀렸을까요 ㅜㅜ

구글링해서 찾은 방식으로 구현하였는데 틀렸다고 나옵니다 ㅜㅜ 샘플은 맞습니다.

다른건 트리를 구성하는 노드 저장하는 데이터 타입과 depth 구할때 저는 bfs 로 했다는것,

parent 정의에서 앞뒤를 반대라는것,,,

제 lca 구현방식을 적용한거라 이정도 다른데 왜 틀렸을까요 ㅜㅜ

고수님들 미리 감사드립니다..

참고한 풀이 : https://devowen.com/274

아래 추가 샘플로도 답이 맞게 나와요..

15
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
3
3 15
4 10
2 14

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class B_4_도로네트워크2 {

	static int N, Q;
	static int[][] p;
	static ArrayList<Node>[] arr;
	static int[] depth;
	static final int MAX_P = 20;
	static int[][] max_arr;
	static int[][] min_arr;
	static boolean[] visit;

	static int max_result;
	static int min_result;

	static class Node {
		int to;
		int length;

		Node(int to, int length) {
			this.to = to;
			this.length = length;
		}
	}

	public static void main(String[] args) throws Exception {

		System.setIn(new FileInputStream("E:/00_sample/11other/B_4.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		StringTokenizer st;

		arr = new ArrayList[N + 1];
		depth = new int[N + 1];
		visit = new boolean[N + 1];

		for (int i = 1; i <= N; i++) {
			arr[i] = new ArrayList<>();
		}

		for (int n = 1; n < N; n++) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			arr[a].add(new Node(b, c));
			arr[b].add(new Node(a, c));

		}

		p = new int[MAX_P + 1][N + 1];
		max_arr = new int[MAX_P + 1][N + 1];
		min_arr = new int[MAX_P + 1][N + 1];

		bfs(1, 0);
		make_parent();

		StringBuilder sb = new StringBuilder();
		Q = Integer.parseInt(br.readLine());
		for (int q = 1; q <= Q; q++) {

			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			int common = lca(a, b);
			sb.append(min_result + " " + max_result + "\n");

		}
		// bw.flush();
		// bw.close();
		System.out.println(sb);

	}

	private static void bfs(int start, int d) {

		depth[start] = d;

		ArrayDeque<Integer> q = new ArrayDeque<>();
		q.offer(start);
		visit[1] = true;

		while (!q.isEmpty()) {

			int here = q.poll();

			for (Node e : arr[here]) {

				int next = e.to;
				int length = e.length;

				if (!visit[next]) {

					depth[next] = depth[here] + 1;
					p[0][next] = here;

					min_arr[0][next] = length;
					max_arr[0][next] = length;

					q.offer(next);
					visit[next] = true;

				}

			}

		}

	}

	private static int lca(int x, int y) {

		max_result = Integer.MIN_VALUE;
		min_result = Integer.MAX_VALUE;

		int tmp;
		if (depth[y] < depth[x]) {
			tmp = x;
			x = y;
			y = tmp;
		}

		for (int i = MAX_P; i >= 0; i--) {
			if ((depth[y] - depth[x]) >= (1 << i)) {

				min_result = Math.min(min_arr[i][y], min_result);
				max_result = Math.max(max_arr[i][y], max_result);
				y = p[i][y];

			}
		}

		if (x == y) {
			return x;
		}

		for (int i = MAX_P; i >= 0; i--) {
			if (p[i][x] != p[i][y]) {

				y = p[i][y];
				x = p[i][x];

				min_result = Math.min(min_result, Math.min(min_arr[i][x], min_arr[i][y]));
				max_result = Math.max(max_result, Math.max(max_arr[i][x], max_arr[i][y]));

				//min_result = Math.min(min_arr[i][y], min_result);
				//max_result = Math.min(max_arr[i][y], max_result);

				//min_result = Math.min(min_arr[i][x], min_result);
				//max_result = Math.min(max_arr[i][x], max_result);

			}
		}

		min_result = Math.min(min_result, Math.min(min_arr[0][x], min_arr[0][y]));
		max_result = Math.max(max_result, Math.max(max_arr[0][x], max_arr[0][y]));
		
	//	min_result = Math.min(min_arr[0][y], min_result);
	//	max_result = Math.max(max_arr[0][y], max_result);

	//	min_result = Math.min(min_arr[0][x], min_result);
	//	max_result = Math.max(max_arr[0][x], max_result);

		return p[0][x];

	}

	private static void make_parent() {

		for (int i = 1; i < MAX_P; i++) {
			for (int j = 1; j <= N; j++) {
				p[i][j] = p[i - 1][p[i - 1][j]];
				max_arr[i][j] = Math.max(max_arr[i - 1][j], max_arr[i - 1][p[i - 1][j]]);
				min_arr[i][j] = Math.min(min_arr[i - 1][j], min_arr[i - 1][p[i - 1][j]]);
			}
		}

	}

}

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

문제

문제

출처

ICPC

3176 도로네트워크 왜틀렸을까요 ㅜㅜ

kally613 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말