J - 道案内 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MiB

AtCoder での提出方法

配布ファイル

  • C または C++ を使用し,navigation_lib.h を include して,Anna と Bruno を 1 つのソースコードの中で実装して提出してください.このジャッジは C / C++ 以外の言語には対応していません.

配点 : 100 点

問題文

Anna は IOI 諸島の住民で,友達の Bruno を IOI 諸島に招待することになった.IOI 諸島は島 1 から島 N までの N 個の島からなる.また,IOI 諸島には N - 1 本の橋があり,橋には 0 から N - 2 までの番号が付けられている.橋 i は島 A_{i} と島 B_{i} を双方向に結ぶ.また,すべての島から橋を通ってすべての島へ行くことができる.Anna の家は島 T にあるが,Bruno は Anna の家のある島の番号を知らない.

Bruno を助けるために,Anna は N 個の島それぞれに 1 個の整数の書かれた旗を 1 本ずつ立てることにした.Anna は Bruno の到着する島の番号を知らない.

Bruno は島 S に船で到着する.島 S に到着した Bruno には,以下の情報が与えられる.

  • 到着した島の番号 S と,島 S に立っている旗に書かれた整数
  • 島 S と橋で直接結ばれているすべての島の番号と,それらの島に立っている旗に書かれた整数

Bruno は島 S から島 T に向かう際に,通る橋の本数が最も少ない経路を通らなければならない.

はたして Bruno は,自分自身に与えられた情報のみを元に,自分が到着した島 S が Anna の家がある島 T かどうかを判定して,S と T が異なる場合は次に向かうべき島を正しく選ぶことができるだろうか.

課題

IOI 諸島の情報が与えられたとき,整数の書かれた旗を立てる Anna の戦略を実装したプログラムを作成せよ.また,島に到着したときに与えられる情報を元に,次の行動を正しく選択する Bruno の戦略を実装したプログラムを作成せよ.

実装の詳細

あなたは同じプログラミング言語で 2 つのファイルを提出しなければならない.

1 つ目のファイルは Anna.c または Anna.cpp という名前である.このファイルは Anna の戦略を実装したファイルであり,以下のルーチンを実装していなければならない.

  • void Anna(int K, int N, int T, int A[], int B[])

    このルーチンは,最初に 1 回だけ呼び出される.

    • 引数 K は小課題の番号 K である.
    • 引数 N は,IOI 諸島の島の数 N である.
    • 引数 T は,Anna の家のある島の番号 T である.
    • 引数 A,引数 B は,長さ N - 1 の配列である.要素 A[i],B[i] は,橋 i が島 A[i] と B[i] を結ぶことを表す (0 \leqq i \leqq N - 2).

また,次のルーチンを呼び出し,島に旗を立てなければならない.

  • void Flag(int I, int V)

    • 引数 I は,Anna が旗を立てる島の番号を表す.
    • 引数 V は,Anna が旗に書く整数を表す.

    ただし,Flag の呼び出しは以下を満たすこと.

    • I は 1 以上 N 以下の整数でなければならない.これを満たさない場合,不正解 [1] となる.
    • Flag を同じ引数 I で 2 回以上呼び出してはならない.これを満たさない場合,不正解 [2] となる.
    • V は 0 以上 N 以下の整数でなければならない.これを満たさない場合,不正解 [3] となる.
    • Flag はちょうど N 回呼び出さなければならない.これを満たさない場合,不正解 [4] となる.

    Flag の呼び出しが不正解と判定された場合,その時点でプログラムの実行は終了される.

2 つ目のファイルは Bruno.c または Bruno.cpp という名前である.このファイルは Bruno の戦略を実装したファイルであり,次のルーチンを実装していなければならない.

  • void Bruno(int K, int S, int F, int L, int P[], int Q[])

    このルーチンは,Anna が呼ばれた後に,1 回だけ呼び出される.

    • 引数 K は小課題の番号 K である.
    • 引数 S は,Bruno の到着した島の番号 S を表す.
    • 引数 F は,島 S に立てられた旗に書かれた整数を表す.
    • 引数 L は,島 S に橋で直接結ばれている島の個数 L である.
    • 引数 P は,長さ L の配列であり,島 S に橋で直接結ばれている島の番号を持つ.
    • 引数 Q は,長さ L の配列であり,要素 Q[j] は,島 P[j] に立てられた旗に書かれた数を表す (0 \leqq j \leqq L - 1).

また,次のルーチンを呼び出して,Bruno が到着した島 S に Anna の家があるかどうかを判定して,もしそうでない場合は次に向かうべき島を正しく選ばなければならない.

  • void Answer(int X)

    • 引数 X は,Bruno が到着した島に Anna の家がある場合は Anna の家がある島の番号 T である.そうでない場合は,Bruno が次に向かうべき島の番号である.

    ただし,Answer の呼び出しは以下を満たすこと.

    • 引数 X は,配列 P のいずれかの要素,または S でなければならない.これを満たさない場合,不正解 [5] となる.
    • Answer を 2 回以上呼び出した場合,不正解 [6] となる.
    • Answer を呼び出さなかった場合,不正解 [7] となる.
    • 島 S に Anna の家があり,引数 X が T でないとき,不正解 [8] となる.
    • 島 S に Anna の家がなく,引数 X が次に向かうべき島でないとき,不正解 [9] となる.

ルーチン Bruno が呼び出された後,答えの判定が行われる.

内部での使用のために他のルーチンを実装したり,グローバル変数を宣言するのは自由である.ただし,提出された 2 つのプログラムは,採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので,各ファイル内のすべてのグローバル変数と内部ルーチンを static で宣言して,他のファイルとの干渉を避ける必要がある.採点時には,このプログラムは Anna 側,Bruno 側として 2 個のプロセスとして実行されるので,Anna 側と Bruno 側でプログラム中のグローバル変数を共有することはできない.

あなたの提出は標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.

コンパイル・実行の方法

作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.

採点プログラムのサンプルは 1 つのファイルからなる.そのファイルは grader.c または grader.cpp である.作成したプログラムをテストするには,次のようにコマンドを実行する.

  • C の場合
gcc -O2 -o grader grader.c Anna.c Bruno.c -lm
  • C++ の場合
g++ -std=c++11 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

コンパイルが成功すれば,grader という実行ファイルが生成される.

実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.

採点プログラムのサンプルの入力

採点プログラムのサンプルは標準入力から以下の入力を読み込む.

  • 1 行目には,整数 N, S , T, K が空白を区切りとして書かれており,IOI 諸島の島の個数が N,Bruno の到着する島の番号が S ,Anna の家のある島の番号が T,小課題の番号が K であることを表す.
  • 続く N - 1 行のうちの i + 1 行目 (0 \leqq i \leqq N - 2) には,整数 A_{i}, B_{i} が空白を区切りとして書かれている.これは,橋 i が島 A_{i} と島 B_{i} を双方向に結ぶことを表す.
  • 次の行には,1 つの整数 Y が書かれている.この整数はこの入力に対する答えである.つまり,Answer の引数として Y を与えた場合に採点プログラムのサンプルが正解と判定し,それ以外の場合に不正解と判定することを表す.

採点プログラムのサンプルの出力

プログラムの実行が正常に終了した場合,採点プログラムのサンプルは標準出力へ以下の情報を 1 行で出力する (引用符は実際には出力されない).

  • 正解の場合,呼び出した関数 Flag の引数 V の最大値が “Accepted : V_max = 2” のように出力される.
  • 不正解の場合,不正解の種類が “Wrong Answer [1]” のように出力される.

制約

すべての入力データは以下の条件を満たす.

  • 2 \leqq N \leqq 100\,000.
  • 1 \leqq S \leqq N.
  • 1 \leqq T \leqq N.
  • 1 \leqq A_{i} \leqq N (0 \leqq i \leqq N - 2).
  • 1 \leqq B_{i} \leqq N (0 \leqq i \leqq N - 2).
  • 1 \leqq K \leqq 4.
  • IOI 諸島のすべての島から橋を通ってすべての島に行くことができる.

小課題

小課題 1 [10 点]

  • K = 1 を満たす.

小課題 2 [15 点]

  • K = 2 を満たす.
  • Flag に渡す引数 V の値は 0 以上 2 以下でなければならない.

小課題 3 [20 点]

  • K = 3 を満たす.
  • Flag に渡す引数 V の値は 0 または 1 でなければならない.
  • ちょうど 2 つの島と橋で直接結ばれている島はない.
  • S \ne T を満たす.

小課題 4 [55 点]

  • K = 4 を満たす.
  • Flag に渡す引数 V の値は 0 または 1 でなければならない.

やりとりの例

採点プログラムのサンプルが読み込む入力の例と,それに対応するルーチンの呼び出しの例を以下に示す.

入力例

5 3 2 1
1 3
3 2
3 4
4 5
2

ルーチンの呼び出しの例

Anna 側 Bruno 側
Anna(...)
Flag(1,1)
Flag(2,1)
Flag(3,0)
Flag(4,0)
Flag(5,1)
Bruno(...)
Answer(2)

この例での Flag の呼び出しは,必ずしも意味のある呼び出しとは限らないことに注意せよ.このとき, Anna(...) と Bruno(...) に渡される引数は次の通りである.

引数 Anna(...)
K 1
N 5
T 2
A \lbrace 1, 3, 3, 4\rbrace
B \lbrace 3, 2, 4, 5\rbrace
引数 Bruno(...)
K 1
S 3
F 0
P \lbrace 2, 1, 4\rbrace
Q \lbrace 1, 1, 0\rbrace

出典

JOI 2014/2015 春季トレーニング合宿 Contest Day3