시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 18 | 15 | 15 | 83.333% |
Wzdłuż rzeki znajduje się n miast. Pomiędzy każdą parą sąsiednich miast wybudowana jest droga, niestety nie zawsze dwukierunkowa, dlatego nie zawsze da się dojechać z każdego miasta do wszystkich innych. Znając, które drogi są wybudowane, chcielibyśmy wiedzieć dla każdego miasta, do ilu innych miast da się z niego dojechać.
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 106), oznaczającą liczbę miast.
W kolejnym wierszu znajduje się n - 1 liczb całkowitych d1, d2, ..., dn-1 (0 ≤ di ≤ 2), gdzie di oznacza połączenie pomiędzy miastem i-tym, a i+1-wszym. Jeśli:
W pierwszym i jedynym wierszu wyjścia powinno znajdować się n liczb całkowitych w1, w2, ..., wn, gdzie wi oznacza liczbę miast, do których da się dojechać z miasta i-tego.
5 0 2 0 1
3 2 2 0 1