Petualangan I - Problem

Ini adalah soal interaktif.

Latar Belakang

Setelah setengah tahun, toko I akhirnya tidak dapat bertahan lagi. Ia memutuskan untuk mengalihkan tokonya dan menjadi penjelajah yang menjelajahi dunia luas yang belum dikenal.

Berdasarkan catatan buku kuno, ia menemukan istana bawah tanah yang dibuat oleh peradaban tak dikenal di pedalaman gurun yang luas. Istana terdiri dari $N$ gua besar dan $M$ lorong dua arah yang menghubungkan gua-gua tersebut. Dengan bantuan buku kuno, I dapat mengenali gua tempatnya berada, tetapi buku itu tidak mencatat struktur hubungan $M$ lorong. Karena itu, ia kesulitan mencari harta tak terhingga yang konon tersembunyi di istana.

Namun, sekarang I menemukan sebuah mekanisme misterius yang dapat memberikan informasi tentang istana. I memutuskan untuk menggunakan mekanisme ini untuk memperoleh struktur hubungan istana. Bantulah ia.

Deskripsi Soal

Istana bawah tanah dapat dimodelkan sebagai graf sederhana tak berarah dengan $N$ simpul dan $M$ sisi (graf sederhana memiliki paling banyak satu sisi langsung di antara sembarang dua simpul). Gua diberi nomor $0\sim n-1$. Saat ini kamu tidak mengetahui sisi-sisinya.

Setiap gua memiliki sebuah sumber cahaya, dengan dua keadaan: menyala atau padam. Sebuah gua hanya diterangi ketika sumber cahayanya menyala. Pada awalnya, semua sumber cahaya padam, dan keadaannya hanya dapat diubah menggunakan mekanisme misterius yang ditemukan I. Secara khusus, mekanisme dapat melakukan empat operasi berikut:

Berikan sebuah nomor $x$ kepada mekanisme. Mekanisme membalik keadaan sumber cahaya gua nomor $x$ serta semua gua yang terhubung langsung dengan gua $x$ melalui lorong. Artinya, sumber cahaya yang semula menyala menjadi padam, dan yang semula padam menjadi menyala.
Berikan sebuah nomor $x$ kepada mekanisme. Mekanisme menampilkan keadaan sumber cahaya gua nomor $x$ saat ini.
Berikan dua nomor $x,y$ kepada mekanisme, yang menyatakan bahwa kamu yakin terdapat lorong yang menghubungkan gua $x$ dan $y$, lalu minta mekanisme mencatatnya.
Berikan sebuah nomor $x$ kepada mekanisme. Mekanisme menentukan apakah semua lorong yang terhubung dengan gua $x$ telah dicatat.

Mekanisme hanya dapat melakukan operasi berikutnya setelah operasi sebelumnya selesai. Mekanisme tidak dapat digunakan sesuka hati, sehingga banyaknya penggunaan setiap operasi dibatasi, berturut-turut oleh $L_m,L_q,M,L_c$. Tugasmu adalah menulis program yang membantu I memutuskan cara menggunakan mekanisme misterius secara wajar untuk menemukan $M$ lorong tersebut dengan benar.

Detail Implementasi

Kamu tidak perlu dan tidak boleh mengimplementasikan fungsi utama. Kamu hanya perlu mengimplementasikan fungsi explore(N, M), dengan $N$ dan $M$ masing-masing menyatakan banyaknya gua dan lorong. Kamu dapat berinteraksi dengan pustaka interaksi dengan memanggil empat fungsi berikut:

1. `modify(x)`

Fungsi ini memerintahkan mekanisme melakukan operasi $1$ dengan nomor $x$.
Kamu harus menjamin $0\le x<N$. Fungsi ini tidak memiliki nilai kembalian.

2. `query(x)`

Fungsi ini memerintahkan mekanisme melakukan operasi $2$ dengan nomor $x$.
Kamu harus menjamin $0\le x<N$. Fungsi mengembalikan $0$ atau $1$, yang menyatakan bahwa sumber cahaya gua $x$ saat ini padam ($0$) atau menyala ($1$).

3. `report(x, y)`

Fungsi ini memerintahkan mekanisme melakukan operasi $3$ dengan nomor $x,y$.
Kamu harus menjamin $0\le x,y<N$ dan $x\ne y$. Fungsi ini tidak memiliki nilai kembalian.

4. `check(x)`

Fungsi ini memerintahkan mekanisme melakukan operasi $4$ dengan nomor $x$.
Kamu harus menjamin $0\le x<N$. Fungsi mengembalikan $0$ atau $1$, dan mengembalikan $1$ jika dan hanya jika semua lorong yang terhubung dengan gua $x$ telah dicatat melalui operasi $3$.

Saat penilaian, pustaka interaksi memanggil explore tepat satu kali.

Dijamin bahwa graf yang digunakan telah ditentukan sepenuhnya sebelum interaksi dimulai dan tidak dikonstruksi secara dinamis berdasarkan proses interaksi dengan programmu. Karena itu, semua operasi interaksi dalam soal bersifat deterministik, dan kamu tidak perlu memperhatikan implementasi khususnya dalam pustaka interaksi.

Data menjamin bahwa selama batas banyaknya pemanggilan dipatuhi, waktu yang diperlukan pustaka interaksi tidak melebihi $1$ detik. Penggunaan memori pustaka interaksi tetap dan tidak melebihi $128$ MB.

Cara Implementasi

Berkas template_explore.cpp/c/pas telah disediakan di direktori kerja peserta. Salin berkas tersebut, ubah namanya menjadi explore.cpp/c/pas, lalu kerjakan solusi berdasarkan berkas itu.

1. Untuk Peserta C++ / C

Pastikan awal programmu memuat #include "explore.h".
Antarmuka fungsi explore yang harus kamu implementasikan adalah:

void explore(int N, int M);

Antarmuka fungsi interaksi yang dapat kamu panggil adalah:

void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);

2. Untuk Peserta Pascal

Perhatian: sintaks implementasi antarmuka dalam Pascal cukup rumit. Kerjakan solusi langsung berdasarkan template_explore.pas yang disediakan, bukan menulis kode dari awal sendiri.
Antarmuka fungsi explore yang harus kamu implementasikan adalah:

procedure _explore(N, M : longint);

Perhatian: nama fungsi di sini adalah _explore, bukan explore. Menggunakan explore menyebabkan kegagalan kompilasi.
Antarmuka fungsi interaksi yang dapat kamu panggil adalah:

procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;

Cara Menguji Program

grader.cpp/c dan graderhelperlib.pas di direktori soal adalah implementasi acuan pustaka interaksi yang kami sediakan. Implementasi pustaka interaksi pada penilaian akhir berbeda dari implementasi acuan ini. Karena itu, solusi peserta tidak boleh bergantung pada implementasi pustaka interaksi.

1. Untuk Peserta C/C++

Gunakan perintah berikut di direktori soal untuk mengompilasi program eksekutabel:
Untuk C:

gcc grader.c explore.c -o explore -O2 -lm

Untuk C++:

g++ grader.cpp explore.cpp -o explore -O2 -lm

2. Untuk Peserta Pascal

Gunakan perintah berikut di direktori soal untuk mengompilasi program eksekutabel:

fpc grader.pas -o"explore" -O2

3. Untuk Program Eksekutabel yang Dihasilkan

Program eksekutabel membaca data dari masukan standar dengan format berikut:

Baris pertama berisi tiga bilangan bulat $L_m,L_q,L_c$. Baris kedua berisi dua bilangan bulat $N,M$, dengan arti seperti yang dijelaskan dalam soal.

Berikutnya terdapat $M$ baris, masing-masing berisi dua bilangan bulat $x,y$ yang mendeskripsikan sebuah lorong antara gua $x$ dan $y$.

Setelah pembacaan selesai, pustaka interaksi memanggil fungsi explore tepat satu kali dan menguji fungsimu menggunakan data masukan. Setelah fungsimu kembali dengan benar, pustaka memeriksa apakah perhitunganmu benar. Jika benar, pustaka mengeluarkan Correct dan informasi terkait banyaknya pemanggilan fungsi interaksi; jika tidak, pustaka mengeluarkan informasi kesalahan yang sesuai.

Contoh Interaksi

Misalkan data yang dibaca program eksekutabel adalah:

100 200 300
3 2
0 1
1 2

Tiga bilangan bulat pada baris pertama masing-masing menyatakan batas banyaknya pemanggilan tiga operasi: modify(x) tidak boleh dipanggil lebih dari $100$ kali, query(x) lebih dari $200$ kali, dan check(x) lebih dari $300$ kali.

Dua bilangan bulat pada baris kedua masing-masing menyatakan banyaknya gua dan lorong, yaitu $N=3,M=2$.

report(x, y) tidak boleh dipanggil lebih dari $M$ kali, yaitu paling banyak $2$ kali pada contoh ini.

Berikut adalah proses interaksi yang benar:

Program peserta	Pustaka interaksi	Penjelasan
	Memanggil `explore(3, 2)`	Memulai pengujian
Memanggil `modify(0)`		Melakukan operasi $1$ pada gua $0$
Memanggil `query(2)`	Mengembalikan $0$	Sumber cahaya gua $2$ saat ini padam
Memanggil `report(0, 1)`		Menemukan dan mencatat lorong $(0,1)$
Memanggil `check(0)`	Mengembalikan $1$	Semua lorong yang terkait dengan gua $0$ telah dicatat
Memanggil `report(2, 1)`		Menemukan dan mencatat lorong $(2,1)$
Selesai berjalan dan kembali	Mencetak `Correct` ke layar	Interaksi berakhir, hasil benar

Penjelasan Berkas yang Disediakan

Di direktori soal ini:

grader.cpp/c dan graderhelperlib.pas adalah implementasi acuan pustaka interaksi yang kami sediakan.
explore.h dan grader.pas adalah berkas header; peserta tidak perlu memperhatikan isi rincinya.
template_explore.cpp/c/pas adalah kode sumber solusi contoh yang kami sediakan.
explore1.in, explore2.in, dan explore3.in adalah masukan contoh untuk pengujian.

Peserta harus mencadangkan seluruh berkas yang disediakan. Penilaian hanya mengambil explore.c/cpp/pas dalam direktori soal ini, dan perubahan terhadap berkas selain program tersebut tidak berpengaruh.

Penilaian

Penilaian akhir hanya mengambil explore.cpp/c/pas. Perubahan terhadap berkas lain dalam direktori peserta tidak berpengaruh pada penilaian.

Pertama, soal ini tunduk pada batasan yang sama dengan soal biasa. Misalnya, kesalahan kompilasi menyebabkan nilai seluruh soal menjadi $0$, sedangkan kesalahan saat berjalan, melampaui batas waktu, melampaui batas memori, dan sebagainya menyebabkan nilai kasus uji terkait menjadi $0$. Kamu hanya boleh mengakses variabel yang kamu definisikan sendiri dan yang diberikan pustaka interaksi beserta ruang memori terkaitnya. Mencoba mengakses ruang lain dapat menyebabkan kesalahan kompilasi atau kesalahan saat berjalan.

Selain kondisi di atas, kamu memperoleh nilai penuh untuk suatu kasus uji jika dan hanya jika:

Setiap pemanggilan fungsimu sah, dan banyaknya pemanggilan modify, query, dan check masing-masing tidak melebihi $L_m,L_q,L_c$.
Karena batas banyaknya pemanggilan report adalah $M$, setiap pemanggilan harus mencatat sebuah sisi baru yang memang ada. Artinya, setiap kali memanggil report(x, y), harus terdapat lorong antara gua $x$ dan $y$, dan sebelum pemanggilan ini belum pernah dipanggil report(x, y) maupun report(y, x).
Fungsi explore yang kamu implementasikan kembali secara normal.
Saat fungsi explore kembali, kamu telah mencatat seluruh $M$ lorong melalui pemanggilan report.

Batasan dan Petunjuk

Soal ini memiliki 25 kasus uji, masing-masing bernilai $4$. Ukuran data dan batasan terkait setiap kasus uji ditunjukkan pada tabel berikut.

Nomor kasus uji	$N=$	$M=$	$L_m=$	$L_q=$	$L_c=$	Sifat khusus
$1$	$3$	$2$	$100$	$100$	$100$	Tidak ada
$2$	$100$	$10N$	$200$	$10^4$	$2M$	Tidak ada
$3$	$200$	$10N$	$200$	$4\times10^4$	$2M$	Tidak ada
$4$	$300$	$10N$	$299$	$9\times10^4$	$2M$	Tidak ada
$5$	$500$	$10N$	$499$	$1.5\times10^5$	$2M$	Tidak ada
$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\times10^4$	$2M$	Tidak ada
$19$	$1004$	$3000$	$10^7$	$5\times10^4$	$2M$	Tidak ada
$20$	$1004$	$3000$	$10^7$	$5\times10^4$	$2M$	Tidak ada
$21$	$50000$	$2N$	$10^7$	$10^7$	$2M$	Tidak ada
$22$	$100000$	$2N$	$10^7$	$10^7$	$2M$	Tidak ada
$23$	$150000$	$200000$	$10^7$	$10^7$	$2M$	Tidak ada
$24$	$200000$	$250000$	$10^7$	$10^7$	$2M$	Tidak ada
$25$	$200000$	$300000$	$10^7$	$10^7$	$2M$	Tidak ada

Sekali lagi, soal menjamin bahwa graf pengujian telah ditentukan sepenuhnya sebelum interaksi dimulai dan tidak dikonstruksi secara dinamis berdasarkan interaksi dengan programmu.

Arti variabel dalam kolom sifat khusus tabel adalah sebagai berikut:

A: dijamin bahwa derajat setiap simpul tepat $1$.

B: dijamin bahwa untuk setiap $x>0$, terdapat tepat satu $y<x$ sehingga gua $x$ dan gua $y$ terhubung langsung oleh sebuah lorong.

C: terdapat suatu permutasi $p_0,p_1,\ldots,p_{N-1}$ dari $0\sim N-1$, sehingga untuk setiap $1\le i<N$ terdapat sebuah lorong antara gua bernomor $p_{i-1}$ dan $p_i$.

D: dijamin bahwa graf terhubung.

Petunjuk: programmu dapat membedakan jenis-jenis data di atas dengan memeriksa digit satuan $N$ yang diberikan.

QOJ.ac

QOJ

#1228. Petualangan I

Latar Belakang

Deskripsi Soal

Detail Implementasi

1. `modify(x)`

2. `query(x)`

3. `report(x, y)`

4. `check(x)`

Cara Implementasi

1. Untuk Peserta C++ / C

2. Untuk Peserta Pascal

Cara Menguji Program

1. Untuk Peserta C/C++

2. Untuk Peserta Pascal

3. Untuk Program Eksekutabel yang Dihasilkan

Contoh Interaksi

Penjelasan Berkas yang Disediakan

Penilaian

Batasan dan Petunjuk

Discussions

About Discussions

Open Discussions 0

Issues

About Issues

Active Issues 0

Closed/Resolved Issues 0

QOJ.ac

QOJ

#1228. Petualangan I

Latar Belakang

Deskripsi Soal

Detail Implementasi

1. modify(x)

2. query(x)

3. report(x, y)

4. check(x)

Cara Implementasi

1. Untuk Peserta C++ / C

2. Untuk Peserta Pascal

Cara Menguji Program

1. Untuk Peserta C/C++

2. Untuk Peserta Pascal

3. Untuk Program Eksekutabel yang Dihasilkan

Contoh Interaksi

Penjelasan Berkas yang Disediakan

Penilaian

Batasan dan Petunjuk

Discussions

About Discussions

Open Discussions 0

Issues

About Issues

Active Issues 0

Closed/Resolved Issues 0

1. `modify(x)`

2. `query(x)`

3. `report(x, y)`

4. `check(x)`