これはインタラクティブ問題です。
五つ組 $(T,I,S_V,S_E,\iota)$ が与えられます。各要素は次のとおりです。
- $T$ は $n$ 頂点の根付き木 $T=(V,E)$ です。$V$ は $T$ の頂点集合、$E$ は $T$ の辺集合です。頂点には $1,2,\ldots,n$ の番号が付けられ、根の番号は $1$ です。
- $I$ は集合で、その要素を情報と呼びます。この集合には、単位元 $\epsilon$ と不正な情報 $\bot$ という、互いに異なる二つの特別な要素があります。
通常の情報は、頂点集合と辺集合という二つの属性を持ちます。特に、単位元は辺集合の属性だけを持ち、不正な情報はこれらのどちらの属性も持ちません。
- 情報 $o\in I\setminus\{\epsilon,\bot\}$ の頂点集合は、$V$ の要素数 $2$ の部分集合です。これを $S_V(o)$ と表し、$S_V(o)\subseteq V$ かつ $|S_V(o)|=2$ を満たします。ここで、二つの集合 $A,B$ の差 $A\setminus B$ は、$A\setminus B=\{x\in A\mid x\notin B\}$ と定義します。
- 情報 $o\in I\setminus\{\bot\}$ の辺集合は、$E$ の部分集合です。これを $S_E(o)$ と表し、$S_E(o)\subseteq E$ を満たします。単位元の辺集合は空、すなわち $S_E(\epsilon)=\varnothing$ と定めます。
- 木の任意の辺 $e\in E$ を $e=(u,v)$ と表すと、その端点を頂点集合、自身を辺集合とする、$e$ に関する情報 $\iota(e)\in I$ が存在します。すなわち、$S_V(\iota(e))=\{u,v\}$、$S_E(\iota(e))=\{e\}$ です。
情報の併合方法は二つあり、それぞれ $R,C$ と表します。任意の $a,b\in I$ に対し、$r=R(a,b)$、$c=C(a,b)$ とおきます。$r,c\in I$ であり、次を満たします。
- 単位元と任意の情報を併合すると、もう一方の情報が得られます。すなわち、$a=\epsilon$ ならば $r=c=b$、$b=\epsilon$ ならば $r=c=a$ です。
- 不正な情報と任意の情報を併合すると、不正な情報が得られます。すなわち、$a=\bot$ または $b=\bot$ ならば $r=c=\bot$ です。
- 残りの場合で、二つの情報の辺集合の共通部分が空でない、または頂点集合の共通部分の要素数が $1$ でないならば、併合結果は不正な情報になります。すなわち、$S_E(a)\cap S_E(b)\ne\varnothing$ または $|S_V(a)\cap S_V(b)|\ne1$ ならば $r=c=\bot$ です。
- それ以外の場合、次が成り立ちます。
$$ S_E(r)=S_E(c)=S_E(a)\cup S_E(b), $$
$$ S_V(r)=S_V(a), $$
$$ S_V(c)=S_V(a)\oplus S_V(b). $$
ここで、$\oplus$ は集合の対称差を表し、$A\oplus B=(A\cup B)\setminus(A\cap B)$ です。
$T$ の二つの頂点間の木上の距離を、その二頂点を端点とする木上の唯一の単純パスに含まれる辺の本数と定義します。
採点パラメータ $M$ と $q$ 個のクエリが与えられます。各クエリでは、木の頂点 $u$ と非負整数 $d$ が与えられます。$T$ の頂点のうち、$u$ からの木上の距離が $d$ 以下の頂点すべてからなる集合を $X$ とし、$X$ の内部の辺集合を $Y=\{(a,b)\in E\mid a,b\in X\}$ とします。$\epsilon$ とすべての $\iota(e)$（$e\in E$）から出発し、$R,C$ を有限回呼び出すことで、$S_E(o)=Y$ を満たす情報 $o\ne\bot$ を必ず得られることが証明できます。
各クエリについて、$R$ と $C$ の呼び出し回数の合計が $M$ 以下という制限の下で、この条件を満たす情報 $o$ を構築してください。特に、$d=0$ の場合は単位元 $\epsilon$ をそのまま返せばよいです。
実装の詳細
プログラムの先頭に #include "count.h" を記述してください。
ヘッダ count.h には、次のものが実装されています。
- 情報に対応するデータ型
infoが定義されています。 - $\epsilon$ に対応する
info型の定数emptyinfoが定義されており、プログラムで直接使用できます。 - 次の二つの情報併合関数が定義・実装されており、プログラムから直接呼び出せます。
info MR(info a,info b);
info MC(info a,info b);- この二つの関数は、それぞれ $R(a,b)$、$C(a,b)$ に対応する情報を返します。
$R(a,b)$ または $C(a,b)$ を呼び出す際には、結果が $\bot$ でないことを保証しなければなりません。そうでない場合、プログラムが異常な動作をする可能性があります。
- 情報が単位元かどうかを判定する次の関数が定義・実装されており、プログラムから直接呼び出せます。
bool isempty(info a);- この関数は、$a$ が単位元である場合かつその場合に限り真を返します。
実装の詳細については、参考のインタラクションライブラリを参照できます。
メイン関数を実装する必要はなく、実装してはいけません。 次の関数を実装してください。
void init(int T, int n, int q, vector<int> fa, vector<info> e, int M);- $T$ はテストケース番号、$n$ は木の頂点数、$q$ はクエリ数、$M$ はそのテストケースの採点パラメータを表します。
faとeの長さはいずれも $n-1$ です。$0\le i<n-1$ に対し、$fa[i]$ と $i+2$ は第 $i$ 辺 $e_i$ の両端点であり、e[i]は問題文の $\iota(e_i)$ に対応するinfo型の要素です。$fa[i]<i+2$ が保証されます。
info ask(int u, int d);- クエリが一つ与えられます。パラメータの意味は問題文を参照してください。関数の終了時に、問題の条件を満たす情報を返してください。
本番のテストでは、各テストケースでインタラクションライブラリは init をちょうど一度呼び出した後、ask を $q$ 回呼び出します。ライブラリは特殊な実装を用い、info 型の変数一つが消費するメモリは常に 12 バイトです。これは配布される参考のインタラクションライブラリとは異なります。 実行時のメモリ使用量を問題の制限内に収めるため、実行中に同時に存在する info 型の変数が多すぎないようにしてください。
呼び出し回数の制限を満たし、isempty を呼び出さない場合、本番のインタラクションライブラリの実行時間は 0.6 秒以下であり、ライブラリ自体のメモリ使用量は 16 MiB 以下であることが保証されます。また、isempty の呼び出しだけを $10^8$ 回実行した場合、本番のインタラクションライブラリの実行時間は 0.25 秒以下であることが保証されます。
配布ファイルには、サンプルプログラムとして count.cpp が含まれています。これを基に本問の実装を進められます。また、バックアップファイル count_backup.h も含まれており、これは count.h と完全に同一であることが保証されます。
プログラムのテスト方法
この問題のディレクトリには、インタラクションライブラリの参考実装として grader.o と checker.o が用意されています。これらは異なる二つのライブラリをコンパイルして得られた、リンク可能なファイルです。本番のテストに用いるライブラリの実装はこれらと異なるため、解法はライブラリの具体的な実装に依存してはいけません。 また、count.h の info 型の具体的な実装にも依存してはいけません。
リンクするために、配布される count.h を変更する必要があります。具体的には、ソースコード count.cpp と grader.o をリンクする場合、count.h の 5 行目をコメントアウトし、4 行目を残してください。checker.o をリンクする場合も同様で、count.h の 4 行目をコメントアウトし、5 行目を残してください。異なるプログラムをコンパイルできるように、count.h の実装を自分で変更してもかまいません。
変更後、この問題のディレクトリで次のコマンドを使用して実行可能プログラムをコンパイルできます。
g++ count.cpp ‐c ‐O2 ‐std=c++14 ‐lm && g++ count.o grader.o ‐o count
g++ count.cpp ‐c ‐O2 ‐std=c++14 ‐lm && g++ count.o checker.o ‐o count1 行目のコマンドは、現在の count.cpp をコンパイルして grader.o とリンクし、実行可能ファイル count を生成します。2 行目は、現在の count.cpp をコンパイルして checker.o とリンクし、実行可能ファイル count を生成します。
上記の方法でコンパイルした実行可能ファイル count は、次のように動作します。
標準入力から次の形式のデータを読み込みます。
- 1 行目には四つの整数 $id,n,q,M$ が与えられ、それぞれテストケース番号、木の頂点数、クエリ数、採点パラメータを表します。
- 2 行目には $n-1$ 個の整数 $p_2,p_3,\ldots,p_n$ が与えられ、それぞれ頂点 $2$ から $n$ の親の番号を表します。ローカルでデバッグする際は、すべての $i\in[2,n]$ について $p_i<i$ を満たすようにしてください。
- 続く $q$ 行には、それぞれ二つの整数 $u,d$ が与えられ、一つのクエリを表します。
読み込み後、インタラクションライブラリがテストを行います。プログラムがライブラリの制限を満たさない場合、対応するエラーメッセージを出力します。そうでない場合、リンクした実行可能ファイルの出力は次のとおりです。
1 行に三つの整数 $C_1,C_2,C_3$ を出力します。それぞれの意味は次のとおりです。
- $C_1$ は
init関数内でインタラクションライブラリの関数を呼び出した総回数です。 - $C_2$ はプログラムの実行中にインタラクションライブラリの関数を呼び出した総回数です。
- $C_3$ は $q$ 回の
askのうち、1 回の呼び出し内でインタラクションライブラリの関数を呼び出した回数の最大値です。 - これら三つの統計量には
MRとMCの呼び出し回数だけを数え、isemptyの呼び出し回数は数えません。
- $C_1$ は
リンクするファイルによって、行える検査も異なります。具体的には次のとおりです。
grader.o：実行時にaskが返す情報の正しさは検査しませんが、インタラクション操作が条件を満たすかを判断するのに役立ちます。このプログラムの実行時間が本番のインタラクションライブラリに最も近いため、実行速度のテストに利用できますが、プログラムの正しさは保証しません。checker.o：実行時にaskが返す情報の正しさを検査し、インタラクション操作が条件を満たすかを判断するのにも役立ちます。また、askが返す情報の正しさも検査します。このプログラムを使うと、解答の正しさを検査できます。
デバッグの際には、実行可能ファイル count に与えるデータが上記の入力形式を満たすようにしてください。そうでない場合、出力結果の正しさは保証されません。
入出力例
入出力例 1
選手用ディレクトリの count/count1.in と count/count1.ans を参照してください。
入出力例 2
選手用ディレクトリの count/count2.in と count/count2.ans を参照してください。
この例は、制約における特別な性質 A を満たします。
入出力例 3
選手用ディレクトリの count/count3.in と count/count3.ans を参照してください。
この例は、制約における特別な性質 B を満たします。
入出力例 4
選手用ディレクトリの count/count4.in と count/count4.ans を参照してください。
小課題
本番の採点では count.cpp だけを収集します。選手用ディレクトリの他のファイルを変更しても、採点結果には影響しません。注意：
- 初期化されていない
info型の変数がemptyinfoであることは保証されません。 info型のメンバ変数へのアクセスや変更を試みないでください。行った場合はインタラクションライブラリへの攻撃とみなされます。initが呼び出される前にMRとMCを呼び出さないでください。未定義動作が起こる可能性があります。- アクセスできるのは、自分で定義した変数とライブラリが返した
info型の変数だけです。他の領域へのアクセスを試みると、コンパイルエラーや実行時エラーが起こる可能性があります。
本問にはまず、通常の問題と同じ制限が適用されます。例えば、コンパイルエラーの場合は問題全体が 0 点となり、実行時エラー、時間制限超過、メモリ制限超過などの場合は対応するテストケースが 0 点となります。
さらに、あるテストケースで不正な関数呼び出しを行ったり、クエリに誤った回答を返したりした場合、そのテストケースは 0 点となります。そうでなければ、init 関数内でインタラクションライブラリの関数を呼び出した回数を $C_1$、全 $q$ 回の ask のうち 1 回の呼び出し内でライブラリの関数を呼び出した回数の最大値を $C_3$ とします。$C_1\le3\cdot10^7$ かつ $C_3$ がそのテストケースの採点パラメータ $M$ 以下であれば、そのテストケースの得点を獲得できます。そうでない場合、そのテストケースの得点は得られません。注意：$C_1,C_3$ を計算する際は MR と MC の呼び出し回数だけを数え、isempty の呼び出し回数は数えません。
制約
すべてのテストケースで、$1\le n\le2\cdot10^5$、$1\le q\le10^6$ を満たします。各クエリでは、$1\le u\le n$、$1\le d\le n-1$ を満たします。
| テストケース | $n=$ | $q=$ | 特別な性質 | $M=$ |
|---|---|---|---|---|
| $1$ | $10^3$ | $10^4$ | $500$ | |
| $2$ | $2000$ | $10^4$ | $500$ | |
| $3,4$ | $10^5$ | $10^6$ | A | $5$ |
| $5,6$ | $6\times10^4$ | $6\times10^4$ | B | $50$ |
| $7$ | $6\times10^4$ | $6\times10^4$ | B | $5$ |
| $8$ | $10^5$ | $10^5$ | B | $5$ |
| $9$ | $7500$ | $5\times10^4$ | C | $500$ |
| $10$ | $10^4$ | $5\times10^4$ | $500$ | |
| $11$ | $15000$ | $5\times10^4$ | $500$ | |
| $12$ | $2\times10^4$ | $5\times10^4$ | $50$ | |
| $13$ | $25000$ | $5\times10^4$ | $5$ | |
| $14$ | $3\times10^4$ | $10^5$ | $5$ | |
| $15$ | $6\times10^4$ | $10^6$ | D | $5$ |
| $16$ | $6\times10^4$ | $10^6$ | $5$ | |
| $17$ | $8\times10^4$ | $10^6$ | $5$ | |
| $18$ | $10^5$ | $10^6$ | $5$ | |
| $19$ | $1.5\times10^5$ | $10^6$ | $5$ | |
| $20$ | $2\times10^5$ | $10^6$ | $1$ |
特別な性質 A：すべての $i\in[1,n-1]$ について、頂点 $i+1$ の親が $i$ であることが保証されます。
特別な性質 B：すべてのクエリで $u=1$ が保証されます。
特別な性質 C：すべてのクエリで $d\le100$ が保証されます。
特別な性質 D：すべてのクエリで $d\ge1000$ が保証されます。