AT_k2pc001_h2 虫歯(Cavity)

[problemUrl]: https://atcoder.jp/contests/k2pc-hard/tasks/k2pc001_h2 **※20:22現在, セット採点がうまく動作していないようです。修正後リジャッジを行います。(恐らくテストケース毎に表示されている結果は正しいです)** **※20:35セット採点データを修正し、リジャッジを行いました。正解しているように見えた解答も不正解扱いになっている可能性があります。ご確認ください。ご迷惑をおかけしました。** kyuridenamidaは, お菓子を食べ過ぎて1本の歯を虫歯にしてしまった. その歯がとても痛むので歯医者さんに治療してもらったところ, 歯の神経のうち $ N $ 箇所を治療してもらえた. kyuridenamidaの歯の神経は, 図$ 1 $に示すように, 深さが$ K $の完全二分木になっている. (二分木については, [Wikipediaのページ](http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8)などを参照せよ.) 図 $ 1 $ 彼の神経を表す二分木で, 深さが $ i $ で左から $ j $ 番目の神経を $ (i,j) $と表す(図 $ 2 $ ). このとき, 根に当たる神経 $ (0,1) $ に, 先祖を遡ってたどり着ける神経を, **虫歯神経**と呼ぶこととする. ただし, 虫歯神経の先祖が既に治療されている場合, その虫歯神経は根の神経 $ (0,\ 1) $ に辿りつけない. また, $ (0,\ 1) $自身が治療されていなければ, $ (0,\ 1) $ が自身にたどり着けるものとする. 図 $ 2 $ 根に辿り着ける虫歯神経の個数の総和を**歯の痛み**とする. あなたの仕事は, kyuridenamidaの虫歯の情報が与えらるので, その歯の痛みをkyuridenamidaに教えて上げることである. 痛みを伝える神経の数を, $ 1 $ 行に出力せよ. (答えが $ 32 $ bit整数型に収まらない可能性があることに注意せよ.) - $ 1\ ≦\ K\ ≦\ 50 $ 歯の神経の深さ - $ 0\ ≦\ N\ ≦\ 10^5 $ 治療済みの神経の個数 - $ 0\ ≦\ p_i\ ≦\ K $ 治療済み神経 $ i $ の深さ - $ 1\ ≦\ q_i\ ≦\ 2^{p_i} $ 治療済み神経 $ i $ の, 深さ $ p_i $での位置 - $ p_i\ =\ p_j $ であれば, $ q_i\ ≠\ q_j $が保証されている. 配点の $ 40% $ 分については, $ N\ ≦\ 1000 $ を満たす. ``` 1 1 1 1 ``` ``` 2 ``` ``` 9 0 ``` ``` 1023 ``` ``` 3 2 1 2 3 7 ``` ``` 8 ``` 入出力例3に対応する図は以下のとおりである. ここで, 図の青丸は治療された神経を表し, 赤の×印は根に辿り着ける虫歯神経を表す. 

N/A

N/A