글 읽기 - 2056 모든 반례 다 맞는데 왜 4%에서 실패할까요?..

subsrltas 1년 전 1

검색해서 찾을 수 있는 반례와 제가 임의로 계속 넣어봤는데 다 맞았습니다..

혹시 안되는 반례가 있을까요?ㅠ

정말 왜 안되는지 이해가 안됩니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        List<Task> list = new ArrayList<>();
        int N = Integer.parseInt(br.readLine());

        int[] indegree = new int[N];
        for (int n = 0; n < N; n++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            list.add(new Task(time));

            int edges = Integer.parseInt(st.nextToken());
            for (int i = 0; i < edges; i++) {
                list.get(Integer.parseInt(st.nextToken()) - 1).edge.add(n);
                indegree[n]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int totalTime = 0;
        while (!queue.isEmpty()) {
            int maxTime = 0;
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                int now = queue.poll();
                maxTime = Math.max(list.get(now).time, maxTime);

                for (Integer e : list.get(now).edge) {
                    indegree[e]--;
                    if (indegree[e] == 0) {
                        queue.offer(e);
                    }
                }
            }
            totalTime += maxTime;
        }
        bw.write(totalTime + System.lineSeparator());
        bw.flush();

        bw.close();
        br.close();
    }

    class Task {
        public int time;
        public List<Integer> edge = new ArrayList<>();

        public Task (int time) {
            this.time = time;
        }
    }
}

sanghyoboy 2달 전 0

5 0

2 0

3 2 1 2

답 : 8

확인해보시겠어요

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

문제

문제

출처

ICPC

2056 모든 반례 다 맞는데 왜 4%에서 실패할까요?..

subsrltas 1년 전 1

sanghyoboy 2달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말