← 返回题目列表

AtCoder · joisc2011_report

report. 报告

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

報告 (Report) - 原题 PDF 第 1 页
原题PDF第3页
報告 (Report) - 原题 PDF 第 2 页
原题PDF第4页
報告 (Report) - 原题 PDF 第 3 页
原题PDF第5页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
                                                                                     Qualifying Trial
                                                              April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                            Contest Day 3 – Report

                         報告(Report)



 情報オリンピック日本委員会は報告・連絡・相談が非常に徹底された組織である.委員会にはN 人が所
属し,すべての人に対しその報告を受ける人(「報告先」と呼ぶ) が1 人ずつ定まっている.
 今,情報オリンピック日本委員会の中で,あるプロジェクトを立ち上げることとなった.このプロジェ
 クトは,仕事1, 仕事2, . . ., 仕事N というN 個の仕事に分けられており,N 人には一つずつ異なる担当が
割り当てられている.N 個の仕事は仕事1 から仕事N まで番号順に処理される.ある仕事の担当者がその
仕事を終えたとき,その人は自分の「報告先」に対して「作業報告」を行う.「作業報告」を受けた人は,そ
れと同一の「作業報告」を自分の「報告先」に対して行う.ただし,同じ「作業報告」を既に自分の「報告
先」にしたことがある場合は,同じ仕事に対する「作業報告」を再びすることはない.これが繰り返され
ることで,委員会中の何人かが「作業報告」を受けることとなる.次の仕事は,前の仕事の「作業報告」
が全て行われてから処理される.


課題

 入力として各仕事の担当者の「報告先」が与えられたとき,それぞれの人が自分の仕事に取りかかる段
階において,受けた「作業報告」の種類の数を出力するプログラムを作成せよ.


制限

    2 ≦N ≦100 000 委員会に所属する人数


入力

 標準入力から以下の入力を読み込め.

    • 1 行目には整数N が書かれており,これは委員会に所属する人数を表す.

    • 続くN 行には各担当者の報告先が書かれている.i+1 行目(1 ≦i ≦N) には1 つの整数Ai (1 ≦Ai ≦N,
       Ai , i) が書かれている. これは,仕事i の担当者の「報告先」が仕事Ai の担当者であることを示す.


出力

 出力はN 行からなる. i 行目(1 ≦i ≦N) に,仕事i の担当者が仕事に取りかかる段階において,受けた
「作業報告」の種類の数を表す1 つの整数を出力せよ.





                          報告– 1 / 3

Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                           Contest Day 3 – Report


採点基準

 採点用データのうち,配点の10%分については,N ≦1 000 を満たす.


入出力の例

 入力例         出力例

 6                    0
 3                    1
 4                    1
 2                    3
 6                    0
 3                    5
 2


 この入力例では,以下のようになる.

   • 仕事1 の担当者が仕事1 に取りかかる.この時点までに仕事1 の担当者が受けた作業報告は0 種類
   である.
   • 仕事1 の作業報告を仕事1 の担当者が仕事3 の担当者に行う.
   • 仕事1 の作業報告を仕事3 の担当者が仕事2 の担当者に行う.
   • 仕事1 の作業報告を仕事2 の担当者が仕事4 の担当者に行う.
   • 仕事1 の作業報告を仕事4 の担当者が仕事6 の担当者に行う.
   • 仕事1 の作業報告を仕事6 の担当者が仕事2 の担当者に行う.
   • 仕事2 の担当者が仕事2 に取りかかる.この時点までに仕事2 の担当者が受けた作業報告は1 種類
   である(仕事1).
   • 仕事2 の作業報告を仕事2 の担当者が仕事4 の担当者に行う.
   • 仕事2 の作業報告を仕事4 の担当者が仕事6 の担当者に行う.
   • 仕事2 の作業報告を仕事6 の担当者が仕事2 の担当者に行う.
   • 仕事3 の担当者が仕事3 に取りかかる.この時点までに仕事3 の担当者が受けた作業報告は1 種類
   である(仕事1).
   • 仕事3 の作業報告を仕事3 の担当者が仕事2 の担当者に行う.
   • 仕事3 の作業報告を仕事2 の担当者が仕事4 の担当者に行う.
   • 仕事3 の作業報告を仕事4 の担当者が仕事6 の担当者に行う.
   • 仕事3 の作業報告を仕事6 の担当者が仕事2 の担当者に行う.
   • 仕事4 の担当者が仕事4 に取りかかる.この時点までに仕事4 の担当者が受けた作業報告は3 種類
   である(仕事1, 2, 3).
   • 仕事4 の作業報告を仕事4 の担当者が仕事6 の担当者に行う.
   • 仕事4 の作業報告を仕事6 の担当者が仕事2 の担当者に行う.
   • 仕事4 の作業報告を仕事2 の担当者が仕事4 の担当者に行う.


                         報告– 2 / 3

Japanese Olympiad in Informatics 2010/2011
                                                                                 Qualifying Trial
                                                          April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                        Contest Day 3 – Report


• 仕事5 の担当者が仕事5 に取りかかる.この時点までに仕事5 の担当者が受けた作業報告は0 種類
 である.
• 仕事5 の作業報告を仕事5 の担当者が仕事3 の担当者に行う.
• 仕事5 の作業報告を仕事3 の担当者が仕事2 の担当者に行う.
• 仕事5 の作業報告を仕事2 の担当者が仕事4 の担当者に行う.
• 仕事5 の作業報告を仕事4 の担当者が仕事6 の担当者に行う.
• 仕事5 の作業報告を仕事6 の担当者が仕事2 の担当者に行う.
• 仕事6 の担当者が仕事6 に取りかかる.この時点までに仕事6 の担当者が受けた作業報告は5 種類
 である(仕事1, 2, 3, 4, 5).
• 仕事6 の作業報告を仕事6 の担当者が仕事2 の担当者に行う.
• 仕事6 の作業報告を仕事2 の担当者が仕事4 の担当者に行う.
• 仕事6 の作業報告を仕事4 の担当者が仕事6 の担当者に行う.





                       報告– 3 / 3