아직 계정이 없으신가요? 회원가입

[21년 재직자 대회 예선] 로드 밸런서 트래픽 예측
난이도
참가자 수
5
제출 수
24
정답률
14.29%
지원 언어
제한시간 : C/C++(2초)/Java/JS/Python(4초)| 메모리 제한 : 1024MB


자율주행 기술은 현대 컴퓨팅의 여러 최첨단 기술에 의존하지만, 이것이 가능하게 하려면 자동차에서 할 수 없는 복잡한 계산과 실시간 도로 정보 확인 등을 중앙 서버에서 빠르고 신속하게 처리할 수 있어야 한다. 이를 위해서 흔히 사용되는 방법은 요청(request)을 처리하는 많은 워커 노드(worker node)들을 두고, 로드 밸런서(load balancer)가 이들 워커 노드에 트래픽을 적절히 분산시키는 것이다.
즉 쉽게 설명하자면, 요청(request)이 들어오면 로드 밸런서가 워커 노드에 적절히 분배 해준다고 생각하면 된다.

현재 총 N개의 서버가 있다. 로드 밸런서와 워커 노드 모두 서버라 지칭하며, 하나의 서버가 로드 밸런서이면서 동시에 워커 노드일 수는 없다. i (1≤i≤N)번째 서버가 로드 밸런서라면 중복을 포함하여 ri개 서버로 트래픽을 분산한다. ri=0이면 i번째 서버는 워커 노드로, 요청을 직접적으로 처리한다. ri>0이라면, i번째 서버는 로드 밸런서로, 아래와 같은 라운드-로빈 (Round-Robin) 방식으로 트래픽을 분산한다.
  • 각각의 로드 밸런서에는 정수형 변수 xi가 있다. 처음에 xi=1이다.
  • 로드 밸런서로 요청이 하나 들어오면, pi,xi번 서버로 트래픽을 전달하고, xi의 값을 (xi mod ri)+1로 바꾼다.

1번 서버는 루트 로드 밸런서로, 모든 요청은 루트 로드 밸런서로만 들어온다. 주어진 트래픽 분산 규칙은 효율적인 분산이 가능하도록 아래 두 조건을 만족한다.
  • 트래픽이 같은 로드 밸런서를 여러 번 거치지 않도록, i→pi,j 간선들로 구성된 그래프에서 사이클이 존재하지 않는다.
  • 1번 서버에 무한히 많은 요청을 보낸다면 모든 서버로 요청이 적어도 1개 이상은 전달된다.

총 K개의 요청이 들어왔다고 할 때, 각 서버로 들어오는 요청의 개수가 몇 개인지를 구하는 프로그램을 작성하라.


제약조건
  • 2≤N≤100,000
  • 1≤K≤1018
  • r1+r2+…+rN≤500,000이다.
  • 모든 1≤i≤N, 1≤j≤ri에 대해, 1≤pi,j≤N이다.
  • i→pi,j 간선들로 구성된 그래프에서 사이클이 존재하지 않는다.
  • 1번 서버에 무한히 많은 요청을 보낸다면 모든 서버로 요청이 적어도 1개 이상은 전달된다.


부분문제
  • (10점) N≤100이고, K≤10,000이다.
  • (90점) 추가 제약 조건 없음


입력형식
첫 번째 줄에 두 정수 N과 K가 공백 하나씩을 사이로 두고 주어진다.
다음 N개의 줄에 ri, pi,1, pi,2,…, pi,ri가 공백 하나씩을 사이로 두고 주어진다.


출력형식
N개의 정수를 공백 하나씩을 사이로 두고 출력한다.
i (1≤i≤N)번째 정수는, i번 서버가 받는 요청의 개수이다.


입력예제1
8 6
3 2 5 8
0
0
0
3 2 4 3
0
0
2 6 7


출력예제1
6 3 0 1 2 1 1 2
로드밸런서의 구조는 아래와 같다.


6개의 요청이 아래와 같이 전달된다.







입력예제2
8 1005
3 2 5 8
0
0
0
3 2 4 3
0
0
2 6 7


출력예제2
1005 447 111 112 335 168 167 335