コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 2332 (記事作成時点)

供養

解法

時刻 $t$ に起こりうるアクションとその順番を固定するために以下のように時刻を変更した操作列を作る
- 時刻 $3S_{i} + 2$ にバス $i$ が発車する
- 時刻 $3T_{i} + 1$ にバス $i$ が到着する
- 時刻 $3X_{j}$ に行動 $j$ を開始する
- 時刻 $3Z_{j}$ に行動 $j$ における現在地を出力する
同時刻に同じ場所にいる2つの行動パターンは以後異なる地点に行くことはないので、代表点を使って集団を考える
- 行動パターン $k$ が代表となる集合を $U_{i}$ とする
- $R_{c} = k$ のとき、都市 $c$ に $U_{k}$ がいるものとする
  - $R_{c} = 0$ ならばその時点において都市 $c$ にいる行動パターンは存在しないとする
- $C_{i} = k$ のとき、その時刻においてバス $i$ に $U_{k}$ が乗っているものとする
現時点での $U_{k}$ の状態を $V_{k}$ とする
ある $u$ が属する集合の代表点を返す関数を $\mathit{Find}(u)$、$u, v$ がそれぞれ属する2つの集合を結合して新たな集合を作り、その代表点を返す関数を $\mathit{Unite}(u, v)$ とする
- $u = 0$ のとき（属する集合が空集合のとき）$\mathit{Unite}(u, v) = \mathit{Find}(v)$
変更後の時刻の早い順に以下のように操作を実施する
- バス $i$ が発車する場合
  - $R_{A_{i}} = k \neq 0$ のとき、$R_{A_{i}} = 0, C_{i} = k, V_{k} = \lbrack A_{i}, B_{i} \rbrack$ とする
- バス $i$ が到着する場合
  - $C_{i} = k \neq 0$ のとき、$R_{B_{i}} = \mathit{Unite}(R_{B_{i}}, k), V_{R_{B_{i}}} = B_{i}$ とする
- 行動 $j$ を開始する場合
  - $V_{j} = Y_{j}, R_{Y_{j}} = \mathit{Unite}(R_{Y_{j}}, j)$ とする
- 行動 $j$ における現在地を出力する場合
  - $V_{\mathit{Find}(j)}$ をクエリ $j$ の答えとして記憶しておく
操作を実施後、記憶していたクエリの答えを順に出力していく