C - Dendrogram - 樹形図
Editorial
/ 
Nathan. O. Davisは情報工学科に所属する学生である。
彼は学科の『人工知能概論』という授業の期末課題のため、 階層的クラスタリングのプログラムを書いている。
クラスタリングとは、オブジェクトの集合をクラスタと呼ばれる複数の部分集合に分ける処理である。
ここで同一のクラスタに所属するオブジェクトは何らかの基準により似ていると判定されたものとなるようにする。
階層的クラスタリングはこれを間接的に行う手法の一つで、オブジェクトの集合を樹形図と呼ばれる木構造で扱う。
ただし、本問題では木の集合も樹形図として扱う。 樹形図はオブジェクト間の類似度を表現する。以下に樹形図の例を示す。
上記の図において、末端の葉は各オブジェクトを表す。
水平の線分はオブジェクトの集合の2つ以上のサブグループへの分割を表す。 別のサブグループに所属するオブジェクトは類似度が低く、
同一のサブグループに所属するオブジェクトは類似度が高いことを表す。
これは水平線が上に位置するほど、その水平線に所属するオブジェクトやオブジェクトの集合の類似度が低いことを表している。
例として、上の図の上から2本目の水平線によって、オブジェクトの集合が3つのクラスタに分けられていることが分かる。
Nathanの書いたプログラムは系統樹を出力すること自体はできるのだが、 2つのバグが含まれていた。
一点目は系統樹が連結になっていない点、つまり出力された系統樹が複数の木構造からなる点である。 これについては本問題では扱わないことにする。
二点目は出力された系統樹の見た目が非常に汚いことである。 具体的には(図:汚い樹形図)のように線分同士が交差してしまっており、
読み取りづらくなってしまっているのである。
あなたの仕事は入力としてNathanの出力した系統樹を受け取り、 綺麗な系統樹を出力するプログラムを書くことである。
ここで綺麗な系統樹とは垂直の線分と水平の線分が接点以外で接触せず、 かつ末端の葉の番号の並びが辞書順で最も若いものとする。
詳細な仕様については入力と出力の欄を参考にせよ。
入力形式は以下の通りである。
初めの行は3つの整数
N
(
1 ≤ N ≤ 100,000
)、
M
(
0 ≤ M < N
)、
Q
(
1 ≤ Q ≤ 1,000
,
Q ≤ N
)からなる。
N
はオブジェクトの数、
M
は水平な線分の数、
Q
はクエリの数を表す。
続く
M
行には水平な線分の情報が与えられる。各行の形式は以下の通りである。
入力の各クエリ
I_{i}
について、 綺麗な系統樹の左から
I_{i}
番目の葉のオブジェクトを表す整数を出力せよ。 ここで
I_{i}
は1から始まるものとする。
本問題は入力データサイズが大きいため、C++のcinやJavaのScannerの使用は速度面で推奨しない。scanf()やStringTokenizerの使用を推奨する。
/ 
Time Limit: 2 sec / Memory Limit: 128 MB
問題文
図：綺麗な樹形図
図：汚い樹形図
入力
N M Q
SplitInfo_{1}
SplitInfo_{2}
...
SplitInfo_{M}
Query_{1}
Query_{2}
...
Query_{Q}
Y L V_1 V_2 ... V_LY ( 0 ≤ Y ≤ 10^9 )は各水平線の上下の位置を表し、 座標が小さいほど上に位置する(類似度が低い)ことを表す。入力中のYは互いに異なる値であることが保証されている。 L (2 ≤ L) は水平線に接続する垂直な線分(オブジェクトまたはオブジェクトの集合)の数を表す。 V_i ( 1 ≤ i ≤ L )はそれぞれ垂直な線分を表す。 各オブジェクトは他と重複しない1から N までの整数で表される。 またオブジェクト集合は、その集合に所属するいずれかのオブジェクトを表す整数で表される。 互いに異なるi, jについて、V_{i} = V_{j}となるようなSplitInfoは存在しない。 続く Q 行には各行にクエリを表す一つの整数 I_{i} が与えられる。
出力
部分点
- 1 ≤ N ≤ 8 を満たす入力にのみ正解した場合、部分点として 50 点が与えられます
入力例 1
3 2 3 10 2 1 2 20 2 3 2 1 2 3
出力例 1
1 2 3
入力例 2
5 2 5 10 3 1 2 4 20 3 2 3 5 1 2 3 4 5
出力例 2
1 2 3 5 4
入力例3
4 1 4 10 2 1 4 1 2 3 4
出力例 3
1 4 2 3
入力例 4
4 3 4 30 2 1 4 20 2 2 4 10 2 3 4 1 2 3 4
出力例 4
1 4 2 3
入力例 5
4 3 4 10 2 1 4 20 2 2 4 30 2 3 4 1 2 3 4
出力例 5
1 2 3 4
入力例 6
4 3 4 10 2 1 2 15 2 1 4 20 2 2 3 1 2 3 4
出力例 6
1 4 2 3
入力例 7
3 2 3 10 2 2 3 20 2 1 2 1 2 3
出力例 7
1 2 3
入力例 8
1 0 1 1
出力例 8
1