글 읽기 - 10%에서 실패입니다

smilesj 6년 전 0

예외 케이스 알 수 있을까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static class Point {
		private int cur;
		private int pre;
		public Point(int cur, int pre) {
			super();
			this.cur = cur;
			this.pre = pre;
		}
		public int getCur() {
			return cur;
		}
		public int getPre() {
			return pre;
		}

	}

	private Map<Integer, ArrayList<Integer>> map;
	private int N;
	private int[] dp;
	private int[] time;
	private int[][] visited;

	public Main(Map<Integer, ArrayList<Integer>> map, int[] time, int N) {
		this.map = map;
		this.N = N;
		this.time = time;
		this.dp = new int[N + 1];
		this.visited = new int[N + 1][N + 1];
	}
	
	public void start() {
		ArrayList<Integer> list = null;
		Stack<Point> stack = new Stack<>();

		for (int i = 1; i <= N; i++) {
			if(visited[i][0] == 1){
				continue;
			}

			stack.add(new Point(i, 0));

			while (!stack.isEmpty()) {
				Point st = stack.peek();
				int c = st.getCur(); // 2
				int p = st.getPre(); // 0

				if(visited[c][p] == 0){
					if(map.containsKey(c)){
						for(int item : map.get(c)){
							if(visited[c][item] == 0){
								stack.add(new Point(item, c));
								if(visited[item][0] == 0){
									stack.add(new Point(item, 0));
								}
							}
						}
					}
					visited[c][p] = 1;
				}else{
					if(p == 0){
						dp[c] += time[c];
					}else{
						dp[p] = Math.max(dp[p], dp[c]);
					}
					stack.pop();
				}
			}
		}
	}

	public void printResult() {
		for (int i = 1; i <= N; i++) {
			System.out.println(dp[i]);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		int[] time = new int[N + 1];
		Map<Integer, ArrayList<Integer>> map = new HashMap<>();
		ArrayList<Integer> list = null;
		String cur = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			boolean first = true;
			while (st.hasMoreTokens()) {
				cur = st.nextToken();
				if ("-1".equals(cur))
					break;

				if (first) {
					time[i + 1] = Integer.parseInt(cur);
					first = false;
					continue;
				}

				if (!map.containsKey(i + 1)) {
					map.put(i + 1, new ArrayList<>());
				}
				list = map.get(i + 1);
				list.add(Integer.parseInt(cur));
			}
		}

		Main q = new Main(map, time, N);
		q.start();
		q.printResult();
	}
}

cbs0615 6년 전 2

1 4 3 2 -1
2 4 -1
1 4 -1
1 -1

cbs0615 6년 전 1

73번 째 줄 밑에 time[c] = 0 추가하니 정답 뜨네요

그런데 이 풀이 방법으로 시간 안에 작동하지 못하는 테스트 케이스를

쉽게 만들 수 있을 것 같습니다.

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

문제

문제

출처

ICPC

10%에서 실패입니다

smilesj 6년 전 0

cbs0615 6년 전 2

cbs0615 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말