소프티어

이 문제 정말 미치는 줄 알았습니다.

분명 설계 잘한거 같은데... 강의 영상을 보고 설계를 비교해도 똑같은거 같은데... 왜 계속 틀리는지.

혹시 싶어서 문제 입력 범위를 보니 들어오는 요청 최대치가 10^18 이 설정되어있는게 보였습니다. 10^16 부터 JS는 BigInt로 설정을 해줘야하기에 그렇게 바꿨습니다.

다행스럽게도 통과되었습니다.

class FIFO {
    constructor(...values) {
        this.head = null
        this.tail = null
        this.length = 0
        values.forEach((value, index) => {
            this.add(value)
        })
    }

    add(value) {
        if (this.length > 0) {
            this.tail[1] = [value, null]
            this.tail = this.tail[1]
        }
        else {
            this.head = this.tail = [value, null]
        }
        this.length++
    }

    pop() {
        if (this.length > 0) {
            const returnValue = this.head[0]
            this.head = this.head[1]
            this.length--
            return returnValue
        }
        else return null
    }
}

const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8').trim().split(/\n+/);
// N: 서버 개수, K: 요청 개수
const [n, K] = input[0].trim().split(/\s+/).map(BigInt);
const serverList = input.slice(1).map(server => server.trim().split(/\s+/).map(Number));
const N = Number(n)
const requestCount = Array(N).fill(0n);
const parentServerCounts = Array(N).fill(0);
serverList.forEach(server => {
    for (let i = 1; i <= server[0]; i++) {
        const serverNum = server[i]
        parentServerCounts[serverNum - 1]++;
    }
})

function processNextServer(serverNum, receivedRequestCount) {
    requestCount[serverNum - 1] += BigInt(receivedRequestCount); // 전달 받은 요청 개수 저장
    parentServerCounts[serverNum - 1]--; // 진입 차수 감소
    return parentServerCounts[serverNum - 1] === 0
}

function passRequestToNextServer(serverNum, fifoList) {
    const totalRequest = requestCount[serverNum - 1]; // 받은 전체 요청
    const nextServerCount = serverList[serverNum - 1][0]; // 다음 서버 개수
    if (nextServerCount === 0) return
    const commonRequestCount = totalRequest / BigInt(nextServerCount) // 공통 전달 개수
    const remainderCount = totalRequest % BigInt(nextServerCount) // 추가 전달 개수

    // 다음 서버 탐색 시작
    for (let i = 1; i <= nextServerCount; i++) {
        const nextServerNum = serverList[serverNum - 1][i]; // 다음 서버 번호
        const isAllParentsProcessed = processNextServer(nextServerNum, commonRequestCount + BigInt(remainderCount >= i ? 1 : 0))
        if (isAllParentsProcessed) {
            fifoList.add(nextServerNum)
        }

    }
}

function bfs(serverNum) {
    const fifoList = new FIFO(serverNum)
    while (fifoList.length > 0) {
        const currentServerNum = fifoList.pop()
        passRequestToNextServer(currentServerNum, fifoList);
    }

}

requestCount[0] = K
bfs(1)
console.log(requestCount.join(' '))




/*
서버에 r, x 값이 주어짐. P도 주어짐. x번째 P의 값이 타겟 서버 번호
r은 P의 개수, 전달 가능한 서버의 개수를 의미. r이 없으면 전달 할 서버가 없으니 워커 노드가 됨
P는 전달 서버 번호. x 를 통해 선택됨. x 초기값은 1
x는 r을 통해 갱신됨. 요청 하나 처리할 때 마다 (x mod r) + 1

Q. 1개씩 시뮬레이션이 되는가?
A. 1 ≤ K ≤ 10^18 의 요청을 처리해야하고, 깊이 또한 고려해야함. 불가능

Q. 요청을 몇개 받았는지가 중요하니. 그냥 x, r 을 통해서 한번에 다 보내 버리면 안되나?
A. (x mod r) + 1 은 그냥 서버 노드를 순회한다고 보면 된다. x는 1로 초기화되는 조건이니, 처음부터 시작함.
r은 P의 개수, 그래서 K // r 이 각 노드 별로 전달되는 공통 요청 개수 이고, k % r이 0, 1, 2 면 0, P1, P1 ~ P2 에 추가 요청 1개씩 전달

Q. 그렇게하면 시간 복잡도는?
A. 그냥 DFS? 순환 없다고 되어있고, 하나의 서버가 여러 서버로 부터 입력을 받을 수 있긴한데
간선이 500,000개라고 주어져 있으니...
위상 정렬을 섞어서 하자


요청 수: 6
서버 정보: 3 2 5 8
6 / 3 = 2 (2, 5, 8 서버에 2개씩)
6 % 3 = 0 (추가 요청 전달 없음)
 */