ABC462B - Gift

考え方

不定長の二次元vectorを扱えるか、という問題。

まず、入力を受け取るのが難しい。
方法は以下。

• $N$ 個の空配列をもっている二次元vectorを作っておく。
• 以下をループする

- $K$ の値を受け取ったら、.resize() を使って a.at(i) の大きさを $K$ に変更する。
- $K$ 個分、通常のvectorと同じように入力を受け取っていく。

それができたら、今度は答えを作っていく。
再び $N$ 個の空配列をもっている二次元vectorを作っておく。
そして、人 $i$ から人 $j$ にギフトを送るなら、人 $j$ は人 $i$ からギフトを受け取るということ。
これを、.emplace_back() で答え用の二次元vectorに入れていく。
$i$ が小さい順に処理することで、自然と結果が昇順に並ぶ。

実際には 0-indexed と 1-indexed の変換をしなくてはいけないことに注意。
すなわち、a.at(i) のデータに j とあるなら、result.at(j-1) に i+1 を入れることになる。

完成したら、今度は出力。
中身の各配列ごとに、まずサイズを出力して、その後中身をスペース区切りで出力する。
最後の出力後のスペースを取り除いてきっちり指定形式にしてもいいし、
AtCoderでは改行前に余計な半角スペースがあっても無視してくれるので、それを利用してもよい。

以下は、C問題以上のレベルの話。
実はこれは有向グラフの隣接リストにおいて、すべての辺の向きを逆転する方法そのものである。
今後もっと難しい問題で使用することになるので、覚えておきたい。

入力例1での動作

入力を受けとる。

n: 4
a: {
     {2},
     {3},
     {2},
     {1, 2, 3}
   }

人数分の要素を持つ、空の二次元vectorを用意する。

result: {
          {},
          {},
          {},
          {}
        }

a[0] のデータを見て、$1$ 人目から受け取る人のデータを更新。
a[i] のデータに j とあるなら、result[j-1] に i+1 を入れる。

a[0]: {2}
result: {
          {},
          {1},
          {},
          {}
        }

a[1] のデータを見て、$2$ 人目から受け取る人のデータを更新。

a[1]: {3}
result: {
          {},
          {1},
          {2},
          {}
        }

a[2] のデータを見て、$3$ 人目から受け取る人のデータを更新。

a[2]: {2}
result: {
          {},
          {1, 3},
          {2},
          {}
        }

a[3] のデータを見て、$4$ 人目から受け取る人のデータを更新。

a[3]: {1, 2, 3}
result: {
          {4},
          {1, 3, 4},
          {2, 4},
          {}
        }

最終的に、result を指示に合わせた形式で出力すればよい。

注意点

特になし。

別解

特になし。