これはインタラクティブ問題です。
偉大な科学者である欣は、世界を支配する強い人工知能「隆」を作ろうとしています。ベトナムのアルゴリズム競技の問題をいくつか訓練データとして入力すると、隆が自動的に新しい問題を生成し、解法も示していることに気づきました。さらに隆は、テストデータの入力の30%をこの問題に帰着させていました。 欣は急いでその問題を次のように書き写しました。 根付き木が与えられ、次の2種類の操作に対応する必要があります。
- 木のパス上の要素の和を求める。
- ある頂点の親を別の頂点に変更する。
「この問題はそれほど強力ではないのに、なぜテストデータの30%の問題を解けるのだろう」と欣は思いました。 訓練結果のページを閉じる直前、欣は突然、隆が示したこの問題では情報をマージするコストが $O(1)$ ではないことに気づきました。 欣は考え込み、自分にはこの問題を解けないことに気づきました。 この問題がどれほど難しいかを知るために、欣はあなたにこの問題を出しました。
問題文
頂点 $1$ を根とする、$n$ 頂点の根付き木を管理してください。初期状態では、すべての $2 \le i \le n$ について、頂点 $i$ の親は $p_i$ であり、$p_i \lt i$ が保証されます。
最初は $n$ 個の集合 $\{1\},\{2\},\cdots,\{n\} $ を持っています。任意の2つの集合 $A$ と $B$ について、$A \cap B=\varnothing$ なら、1回の操作で $|A|+|B|$ のコストを払い、集合 $A \cup B$ を得ることができます。
その後、$q$ 回の操作があります。各操作は次の2種類のいずれかです。
0 a b：木の頂点 $a$ から $b$ へのパス上の頂点の集合を $S$ とします。$S$ を $\cup_{i=1}^{k}A_i$ と表してください。ただし、$A_i$ はすでに得た集合であり、$\forall i \neq j,A_i \cap A_j=\varnothing$ を満たす必要があります。$(A_1,A_2,\cdots,A_k) $ で1回の問い合わせに答えるコストは $k$ です。1 a b：頂点 $a$ の親を $b$ に変更します。$a \gt 1$ であり、変更後もこれらの $n$ 頂点が木をなすことが保証されますが、$a \gt b$ は保証されません。この操作中に、後の問い合わせに備えて新しい集合をいくつか生成してもかまいません。
プログラム全体の実行中にかかった総コストを $C_1$、1回の操作にかかったコストの最大値を $C_2$ とします。各小課題では、$C_1,C_2$ の大きさに応じて所定の方法で得点を計算します。
実装の詳細
プログラムの先頭に #include "long.h" を必ず記述してください。
このヘッダーファイルでは、得られた集合を格納するデータ型 infoset が定義されています。
この型には集合の大きさを表すメンバー関数 size() があります。また、ヘッダーファイルには空集合を表す定数 emptyset が用意されています。
さらに、次の関数を呼び出せます。
infoset merge(const infoset&A,const infoset&B);
- 所定のコストで新しい集合 $A \cup B$ を生成します。
- 同じ集合を繰り返し生成することもできますが、そのたびにコストが加算されることに注意してください。
void report(infoset A);
- この関数は問い合わせ操作の間だけ呼び出せます。コスト $1$ を払い、最終的な和集合に集合 $A$ を追加することを表します。
main 関数を実装する必要はなく、実装してはいけません。次の関数を実装してください。
void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);
- $q$ 回の操作が始まる前に、情報の前処理を行えます。
- この関数でかかったコストは、1回の操作にかかったコストの最大値には含まれませんが、プログラム全体の実行中にかかった総コストには含まれます。
idは小課題番号、nは頂点数、qは操作数です。dadのサイズは $n-1$ で、dad[i]は初期状態での頂点 $i+2$ の親を表します。veのサイズは $n$ で、ve[i]は初期集合 $\{i+1\}$ を表します。
void modify(int x,int y);
- 変更操作を1回実行し、頂点 $x$ の親を頂点 $y$ に変更します。
void ask(int x,int y);
- 問い合わせ操作を1回実行し、$x$ から $y$ への木のパスの情報を求めます。
reportを何回か呼び出して問い合わせに答えてください。問い合わせの終了時に、インタラクションライブラリが、報告したすべての集合 $A$ が条件を満たすかを検査します。
採点時には、インタラクションライブラリが最初に init を1回呼び出し、その後 modify と ask を合計 $q$ 回呼び出します。
木の形と実行される操作は、インタラクション開始前にすべて確定しており、あなたのプログラムとのやり取りに応じて動的に構成されることはありません。したがって、問題のインタラクティブな操作はすべて決定的であり、ライブラリ内での具体的な実装を気にする必要はありません。
採点時には、インタラクションライブラリは特殊な実装を使用し、infoset 型の変数1個は常に $8$ バイトのメモリを使用します。実行中に infoset 型の変数が同時に存在しすぎないようにしてください。
呼び出し回数の制限内では、インタラクションライブラリの実行時間は2秒以下であり、ライブラリ自体のメモリ使用量は16MB以下であることが保証されます。
プログラムのテスト方法
配布ファイルの grader.cpp は、インタラクションライブラリの参考実装です。最終的な採点で使われるライブラリの実装はこの参考実装と異なるため、解法はライブラリの実装に依存してはいけません。
次のコマンドでコンパイルし、実行可能プログラムを作成してください。
g++ grader.cpp long.cpp -o long -static -O2 -std=c++14
コンパイルされた実行可能プログラムについては、次のとおりです。
実行可能ファイルは、標準入力から次の形式のデータを読み込みます。
- 1行目には、小課題番号を表す整数 $id$ が含まれます。
- 2行目には、頂点数と操作数を表す2つの整数 $n,q$ が含まれます。
- 3行目には、頂点 $2$ から $n$ の親の頂点番号を順に表す $n-1$ 個の整数が含まれます。
- 続く $q$ 行は、それぞれ3つの整数 $op,x,y$ を含み、1回の操作を表します。$op=0$ は問い合わせ操作、$op=1$ は変更操作を表します。
- 入力が終わると、インタラクションライブラリは
initをちょうど1回、modifyまたはaskを $q$ 回呼び出し、入力データを使って実装した関数をテストします。正常に実行されると、プログラムは複数行を出力し、各行の数値は各問い合わせ操作への回答を表します。最後の行には、プログラムの総コストと1回の操作のコストの最大値をそれぞれ表す2つの整数 $W_1,W_2$ が含まれます。
配布ファイルには4組のサンプルファイルが含まれ、そのうち4組目は小課題2の特殊な性質を満たします。 サンプルをテストするときは、出力ファイルの最終行の比較結果を無視してください。インタラクションライブラリが出力する最終行は、問い合わせの結果ではなくプログラムの実行コストだからです。
小課題
この問題には、まず通常の問題と同じ制限が適用されます。 例えば、コンパイルエラーなら問題全体が $0$ 点となり、実行時エラー、時間制限超過、メモリ制限超過などが起きると、該当するテストケースが $0$ 点となります。自分で定義した変数とインタラクションライブラリが提供する変数、およびそれらに対応するメモリ領域にだけアクセスできます。他の領域へのアクセスを試みると、コンパイルエラーや実行時エラーになることがあります。
以上の条件を前提として、あるテストケースで不正な関数呼び出しをした場合、正常に終了しなかった場合、または問い合わせに誤った回答をした場合、そのテストケースは $0$ 点となります。それ以外の場合、プログラムのコストに応じて、次の2通りの方法で採点します。
- 採点方法1：$W_1 \gt 6 \cdot 10^8$ なら、そのテストケースは $0$ 点です。それ以外の場合、そのテストケースの得点は $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10}$ に、そのテストケースが属する小課題の配点を掛けた値です。
- 採点方法2：$W_2 \gt 2 \cdot 10^4$ なら、そのテストケースは $0$ 点です。それ以外の場合、そのテストケースの得点は $\frac{5000}{max(W_2,5000)}$ に、そのテストケースが属する小課題の配点を掛けた値です。
小課題ごとに異なる採点方法を使います。小課題の得点は、その中のすべてのテストケースの得点の最小値です。
制約
すべてのテストケースで $1 \le n,q \le 10^5$ が保証されます。
| 小課題番号 | $n,q \le$ | 特殊な性質 | 採点方法 | 配点 |
|---|---|---|---|---|
| $1$ | $100$ | なし | .h=2 1 | $10$ |
| $2$ | .h=4 $10^5$ | .h=2 あり | $20$ | |
| $3$ | 2 | $20$ | ||
| $4$ | .h=2 なし | 1 | $30$ | |
| $5$ | 2 | $20$ |
特殊な性質：どの時点でも、頂点 $1$ 以外の各頂点は子を高々1つしか持たないことが保証されます。
後書き
欣は、あなたが5時間たってもこの問題を解けなかったことを知り、隆の能力に大いに満足しました。しかし翌朝起きると、欣は突然、隆の解法の計算量の証明が間違っていることに気づきました。