QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Interactive

#1228. I 君の探検

Statistics

これはインタラクティブな問題です。

背景

半年が過ぎ、I 君の店はとうとう経営を続けられなくなりました。彼は店を譲り、探検家となって未知の広大な世界を探索することにしました。

古文書の記述を頼りに、彼は大砂漠の奥地で、未知の文明が造った地下宮殿を発見しました。宮殿は $N$ 個の大きな洞窟と、それらを結ぶ $M$ 本の双方向の通路からなります。I 君は古文書を使って自分がいる洞窟を識別できますが、古文書には $M$ 本の通路の接続関係が記録されていないため、宮殿に隠されているという無尽蔵の財宝を探すのは困難です。

しかし、I 君は宮殿の情報を得られる不思議な仕掛けを発見しました。この仕掛けを使って宮殿の接続関係を調べようとしています。彼を手伝ってください。

問題文

地下宮殿は、$N$ 頂点 $M$ 辺の単純無向グラフとして表せます（単純グラフでは、任意の 2 頂点間に直接結ぶ辺が高々 1 本しかありません）。洞窟には $0 \sim n-1$ の番号が付いています。現在、どの辺が存在するかは分かりません。

各洞窟には光源が 1 つあり、点灯と消灯の 2 状態を持ちます。光源が点灯しているときにだけ、その洞窟は照らされます。初期状態では、すべての光源は消灯しており、光源の状態は I 君が発見した不思議な仕掛けでしか変更できません。具体的には、仕掛けを使って次の 4 種類の操作を行えます。

  1. 番号 $x$ を仕掛けに与えます。仕掛けは、洞窟 $x$ と、洞窟 $x$ に通路で直接つながっている洞窟の光源の状態を反転します。すなわち、点灯していた光源は消灯し、消灯していた光源は点灯します。
  2. 番号 $x$ を仕掛けに与えます。仕掛けは、洞窟 $x$ の光源の現在の状態を表示します。
  3. 2 つの番号 $x,y$ を仕掛けに与えます。これは、洞窟 $x$ と洞窟 $y$ を結ぶ通路が存在することを確かめたと伝え、仕掛けに記録させる操作です。
  4. 番号 $x$ を仕掛けに与えます。仕掛けは、洞窟 $x$ につながる通路がすべて記録済みかどうかを判定します。

仕掛けは、前の操作が終わってから次の操作を行えます。自由に使えるわけではなく、各操作の使用回数の上限は順に $L_m,L_q,M,L_c$ です。不思議な仕掛けを適切に使い、$M$ 本の通路を正しく見つけられるよう I 君を助けるプログラムを書いてください。

実装の詳細

メイン関数を実装する必要はなく、実装してはいけません。実装するのは関数 explore(N, M) だけです。 $N,M$ は洞窟数と通路数を表します。次の 4 つの関数を呼び出して、インタラクションライブラリとやり取りできます。

modify(x)

  • 番号 $x$ を指定して、仕掛けに操作 1 を行わせます。
  • $0 \leq x<N$ を保証する必要があります。戻り値はありません。

query(x)

  • 番号 $x$ を指定して、仕掛けに操作 2 を行わせます。
  • $0 \leq x<N$ を保証する必要があります。現在の洞窟 $x$ の光源が消灯している場合は $0$、点灯している場合は $1$ を返します。

report(x, y)

  • 番号 $x,y$ を指定して、仕掛けに操作 3 を行わせます。
  • $0 \leq x,y<N$ かつ $x \ne y$ を保証する必要があります。戻り値はありません。

check(x)

  • 番号 $x$ を指定して、仕掛けに操作 4 を行わせます。
  • $0 \leq x<N$ を保証する必要があります。戻り値は $0$ または $1$ であり、洞窟 $x$ につながるすべての通路が操作 3 によって記録済みのとき、かつそのときに限り $1$ を返します。

採点時、インタラクションライブラリは explore をちょうど 1 回呼び出します。

グラフはインタラクションの開始前に完全に決定されており、あなたのプログラムとのやり取りに応じて動的に構成されることはありません。したがって、各操作は決定的であり、ライブラリ内部での具体的な実装を気にする必要はありません。

呼び出し回数の制限内であれば、インタラクションライブラリの実行に必要な時間は 1 秒以下であることが保証されます。ライブラリが使用するメモリ量は固定されており、128 MB 以下です。

実装方法

選手用作業ディレクトリには template_explore.cpp/c/pas が用意されています。このファイルをコピーし、explore.cpp/c/pas に名前を変え、それを基に解答してください。

C++ / C の場合

  • プログラムの先頭に #include "explore.h" があることを確認してください。
  • 実装する関数 explore のインターフェースは次のとおりです。
void explore(int N, int M);
  • 呼び出せるインタラクション関数のインターフェースは次のとおりです。
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);

Pascal の場合

  • Pascal ではインターフェースの実装に必要な構文が複雑です。最初から自分でコードを書くのではなく、配布された template_explore.pas を直接基にして解答してください。
  • 実装する関数 explore のインターフェースは次のとおりです。
procedure _explore(N, M : longint);
  • 関数名は explore ではなく _explore であることに注意してください。explore を使うとコンパイルエラーになります。
  • 呼び出せるインタラクション関数のインターフェースは次のとおりです。
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;

プログラムのテスト方法

問題ディレクトリ内の grader.cpp/c と graderhelperlib.pas は、提供するインタラクションライブラリの参考実装です。最終的なテストで使うライブラリの実装は参考実装と異なります。そのため、解法をライブラリの実装に依存させてはいけません。

C/C++ の場合

問題ディレクトリ内で次のコマンドを使ってコンパイルし、実行ファイルを作成してください。

  • C の場合：
gcc grader.c explore.c -o explore -O2 -lm
  • C++ の場合：
g++ grader.cpp explore.cpp -o explore -O2 -lm

Pascal の場合

問題ディレクトリ内で次のコマンドを使ってコンパイルし、実行ファイルを作成してください。

fpc grader.pas -o"explore" -O2

作成した実行ファイルについて

  • 実行ファイルは、次の形式のデータを標準入力から読み込みます。

1 行目には 3 つの整数 $L_m,L_q,L_c$、2 行目には 2 つの整数 $N,M$ が与えられます。意味は問題文のとおりです。

続く $M$ 行には、それぞれ 2 つの整数 $x,y$ が与えられ、洞窟 $x$ と洞窟 $y$ を結ぶ通路を表します。

  • 読み込みが終わると、ライブラリは関数 explore をちょうど 1 回呼び出し、入力データを使ってあなたの関数をテストします。関数が正常に戻ると、ライブラリは計算が正しいか判定し、正しければ Correct とインタラクション関数の呼び出し回数に関する情報を出力します。それ以外の場合は、対応するエラーメッセージを出力します。

インタラクション

実行ファイルが次のデータを読み込んだとします。

100 200 300
3 2
0 1
1 2

1 行目の 3 つの整数は、3 種類の操作の呼び出し回数の上限を表します。すなわち、modify(x) は $100$ 回以下、query(x) は $200$ 回以下、check(x) は $300$ 回以下しか呼び出せません。

2 行目の 2 つの整数は、洞窟数と通路数を表し、$N=3$、$M=2$ です。

report(x, y) の呼び出し回数は $M$ 回以下である必要があり、この例では $2$ 回以下です。

以下は正しいインタラクションの例です。

選手のプログラム インタラクションライブラリ 説明
explore(3, 2) を呼び出す テスト開始
modify(0) を呼び出す 洞窟 $0$ に対して操作 1 を行う
query(2) を呼び出す $0$ を返す 現在、洞窟 $2$ の光源は消灯している
report(0, 1) を呼び出す 通路 $(0,1)$ を発見し、記録する
check(0) を呼び出す $1$ を返す 洞窟 $0$ に関係する通路はすべて記録済み
report(2, 1) を呼び出す 通路 $(2,1)$ を発見し、記録する
実行を終了して戻る 画面に Correct を出力する インタラクション終了、結果は正しい

配布ファイルの説明

問題ディレクトリ内には、次のファイルがあります。

  1. grader.cpp/c と graderhelperlib.pas は、提供するインタラクションライブラリの参考実装です。
  2. explore.h と grader.pas はヘッダファイルです。内容を気にする必要はありません。
  3. template_explore.cpp/c/pas は、提供する解答用ソースコードの例です。
  4. explore1.in、explore2.in、explore3.in は、テストに使えるサンプル入力です。

配布されたすべてのファイルをバックアップしてください。採点では、この問題のディレクトリ内の explore.c/cpp/pas だけを回収します。それ以外のファイルを変更しても採点には反映されません。

小課題

最終的な採点では explore.cpp/c/pas だけを回収します。選手用ディレクトリ内の他のファイルを変更しても、採点には反映されません。

まず、通常の問題と同じ制限が適用されます。例えば、コンパイルエラーの場合は問題全体が 0 点となり、実行時エラー、時間制限超過、メモリ制限超過などの場合は、対応するテストケースが 0 点になります。アクセスできるのは、自分が定義した変数とライブラリが提供する変数、およびそれらに対応するメモリ領域だけです。それ以外の領域にアクセスしようとすると、コンパイルエラーや実行時エラーが発生することがあります。

上の条件に加え、あるテストケースで満点を獲得できるのは、次の条件をすべて満たすとき、かつそのときに限ります。

  1. 関数の呼び出しが毎回正しく、modify、query、check の呼び出し回数が、それぞれ $L_m,L_q,L_c$ 以下であること。
  2. report の呼び出し回数の上限は $M$ なので、毎回、新しく、かつ実在する辺を記録しなければなりません。すなわち、report(x, y) を呼び出すときは、洞窟 $x$ と洞窟 $y$ を結ぶ通路が存在し、それ以前に report(x, y) も report(y, x) も呼び出されていない必要があります。
  3. 実装した関数 explore が正常に戻ること。
  4. explore が戻る時点で、report の呼び出しによって $M$ 本の通路をすべて記録していること。

制約

全部で 25 個のテストケースがあり、各テストケースは 4 点です。各テストケースの規模と制限は次の表のとおりです。

テストケース番号 $N=$ $M=$ $L_m=$ $L_q=$ $L_c=$ 特別な性質
$1$ $3$ $2$ $100$ $100$ $100$ なし
$2$ $100$ $10N$ $200$ $10^4$ $2M$ なし
$3$ $200$ $10N$ $200$ $4\times 10^4$ $2M$ なし
$4$ $300$ $10N$ $299$ $9\times 10^4$ $2M$ なし
$5$ $500$ $10N$ $499$ $1.5\times 10^5$ $2M$ なし
$6$ $59998$ $N/2$ $17N$ $17N$ $0$ A
$7$ $99998$ $N/2$ $18N$ $18N$ $0$ A
$8$ $199998$ $N/2$ $19N$ $19N$ $0$ A
$9$ $199998$ $N/2$ $19N$ $19N$ $0$ A
$10$ $99997$ $N-1$ $18N$ $18N$ $0$ B
$11$ $199997$ $N-1$ $19N$ $19N$ $0$ B
$12$ $99996$ $N-1$ $10^7$ $10^7$ $2M$ C
$13$ $199996$ $N-1$ $10^7$ $10^7$ $2M$ C
$14$ $199996$ $N-1$ $10^7$ $10^7$ $2M$ C
$15$ $99995$ $N-1$ $10^7$ $10^7$ $2M$ D
$16$ $99995$ $N-1$ $10^7$ $10^7$ $2M$ D
$17$ $199995$ $N-1$ $10^7$ $10^7$ $2M$ D
$18$ $1004$ $2000$ $10^7$ $5\times 10^4$ $2M$ なし
$19$ $1004$ $3000$ $10^7$ $5\times 10^4$ $2M$ なし
$20$ $1004$ $3000$ $10^7$ $5\times 10^4$ $2M$ なし
$21$ $50000$ $2N$ $10^7$ $10^7$ $2M$ なし
$22$ $100000$ $2N$ $10^7$ $10^7$ $2M$ なし
$23$ $150000$ $200000$ $10^7$ $10^7$ $2M$ なし
$24$ $200000$ $250000$ $10^7$ $10^7$ $2M$ なし
$25$ $200000$ $300000$ $10^7$ $10^7$ $2M$ なし

繰り返しますが、テストに使うグラフは、インタラクションの開始前に完全に決定されており、あなたのプログラムとのやり取りに応じて動的に構成されることはありません。

表の「特別な性質」の記号は、次の意味を持ちます。

A：すべての頂点の次数がちょうど $1$ であることが保証されます。

B：各 $x>0$ について、$y<x$ かつ洞窟 $x$ と洞窟 $y$ が通路で直接つながっているような $y$ が、ちょうど 1 つ存在することが保証されます。

C：$0 \sim N-1$ の順列 $p_0,p_1,\ldots,p_{N-1}$ が存在し、任意の $1 \leq i<N$ について、洞窟 $p_{i-1}$ と洞窟 $p_i$ を結ぶ通路が存在します。

D：グラフが連結であることが保証されます。

  • ヒント：与えられた $N$ の 1 の位を調べることで、上記のデータの種類を区別できます。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.
العربية English Español Français 日本語 한국어 Türkçe 简体中文 繁體中文

Made with ❤️ by Qingyu✨ | Contact us: [email protected]

Server Time: 2026-10-28 06:24:28 (UTC+8)