← 返回题目列表

AtCoder · joisc2020_e

E. 在 Joitter 上交朋友很有趣

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

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

ジョイッターで友だちをつくろう (Making Friends on Joitter is Fun) - 原题 PDF 第 1 页
原题PDF第1页
ジョイッターで友だちをつくろう (Making Friends on Joitter is Fun) - 原题 PDF 第 2 页
原题PDF第2页
ジョイッターで友だちをつくろう (Making Friends on Joitter is Fun) - 原题 PDF 第 3 页
原题PDF第3页
ジョイッターで友だちをつくろう (Making Friends on Joitter is Fun) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                  Contest Day 2 – Making Friends on Joitter is Fun

 ジョイッターで友だちをつくろう(Making Friends on Joitter is Fun)



  ジョイッター(Joitter) は,短い日記の気軽な投稿や写真の共有を通して,知り合いとのインターネット上

でのコミュニケーションをより快適にする,話題沸騰中のソーシャル・ネットワーキング・サービス(SNS)

である.

 ジョイッターでは,自分以外のユーザをフォローすることができる.あるユーザa がある他のユーザb を

フォローすると,ユーザa のアカウントからユーザb の発言を閲覧することができるようになる.このと

き,ユーザb がユーザa をフォローすることも,しないことも可能である.ただし,自分自身をフォローし

たり,あるユーザa がユーザb を2 回以上フォローすることはできない.

 今,人1, 2, . . . , N からなるN 人のユーザがJoitter に新規登録した.現時点ではどのユーザも他のユーザ

を誰もフォローしていない.

 N 人は仲良くなるために,これからM 日間にわたり,1 日1 回ずつあるユーザが別のユーザをフォロー
することにした.i 日目(1 ≦i ≦M) には,人Ai が人Bi を新たにフォローする.
   Joitter では,ユーザ間のフォローを増やすため,M 日間のうちのある1 回,サービス内で交流イベント

を開催しようと計画している.交流イベントは,以下のようにして行われる.

    1. N 人のユーザのうち1 人(以下,人x と呼ぶことにする) を選ぶ.

    2. 人x が現在フォローしているユーザのうち1 人(以下,人y と呼ぶことにする) を選ぶ.

    3. 人x が現在フォローしておらず,人y が現在フォローしている人x 以外のユーザで,そのユーザも人

      y を現在フォローしているもののうち1 人(以下,人z と呼ぶことにする) を選ぶ.

    4. 人x が人z をフォローする.

    5. 条件を満たす人x,人y,人z の組が選べなくなるまで以上を繰り返す.

 交流イベントをいつ行うかはまだ決まっていない.そこで,M 日間の各日において,あるユーザが別の

ユーザをフォローした後に交流イベントを開催したとき,交流イベントが終了した直後にN 人がフォロー

している人数の合計の最大値を求めたい.ただし,交流イベントはその日のうちに終了するものとする.

 ユーザの人数とM 日間のフォローの情報が与えられたとき,各日における交流イベントが終了した直後

のN 人がフォローしている人数の合計の最大値を求めるプログラムを作成せよ.





                ジョイッターで友だちをつくろう– 1 / 4

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                  Contest Day 2 – Making Friends on Joitter is Fun



入力


 入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.


    N M

      A1 B1
                                 ...

     AM BM


出力

 M 行出力せよ.i 行目(1 ≦i ≦M) には,i 日目にあるユーザが別のユーザをフォローした後に交流イベ

ントを開催したとき,交流イベントが終了した直後にN 人がフォローしている人数の合計の最大値を出力

せよ.


制約

    • 2 ≦N ≦100 000.

    • 1 ≦M ≦300 000.
    • 1 ≦Ai ≦N (1 ≦i ≦M).
    • 1 ≦Bi ≦N (1 ≦i ≦M).
    • Ai , Bi (1 ≦i ≦M).
    • (Ai, Bi) , (Aj, Bj) (1 ≦i <  j ≦M).


小課題

    1. (1 点) N ≦50.

    2. (16 点) N ≦2000.

    3. (83 点) 追加の制限はない.





                ジョイッターで友だちをつくろう– 2 / 4

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                  Contest Day 2 – Making Friends on Joitter is Fun



入出力例

  入力例1              出力例1

   4 6                            1

   1 2                            2

   2 3                            4

   3 2                            4

   1 3                            5

   3 4                            9

   4 3

    • 1 日目に人1 が人2 をフォローする.この後交流イベントを開いても,新たに誰かが他の誰かをフォ

   ローすることはなく,フォロー人数の合計は1 である.

    • 2 日目に人2 が人3 をフォローする.この後交流イベントを開いても,新たに誰かが他の誰かをフォ

   ローすることはなく,フォロー人数の合計は2 である.

    • 3 日目に人3 が人2 をフォローする.この後交流イベントを開くと,例えば人1 が人3 をフォローす

   る.この場合フォロー人数の合計は4 となり,最大である.

    • 4 日目に人1 が人3 をフォローする.この後交流イベントを開いても,新たに誰かが他の誰かをフォ

   ローすることはなく,フォロー人数の合計は4 となる.

    • 5 日目に人3 が人4 をフォローする.この後交流イベントを開いても,新たに誰かが他の誰かをフォ

   ローすることはなく,フォロー人数の合計は5 となる.

    • 6 日目に人4 が人3 をフォローする.この後交流イベントを開くと,例えば人1 が人4 をフォロー

   し,人2 が人4 をフォローし,人4 が人2 をフォローする.この場合フォロー人数の合計は9 とな

   り,最大である.





                ジョイッターで友だちをつくろう– 3 / 4

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                      Spring Training Camp/Qualifying Trial

                                               March 20–23, 2020 (Komaba, Tokyo)


                                              Contest Day 2 – Making Friends on Joitter is Fun


入力例2              出力例2

6 10                           1

1 2                            2

2 3                            3

3 4                            4

4 5                            5

5 6                            7

6 5                            11

5 4                            17

4 3                            25

3 2                            30

2 1





              ジョイッターで友だちをつくろう– 4 / 4