Bạn có biết công ty Just Odd Inventions không? Công ty này chỉ chuyên tạo ra những phát minh kỳ lạ; chúng ta gọi tắt là JOI.

Trong một phòng thí nghiệm của JOI có một mạch điện phức tạp gồm \(N\) nút và \(M\) điện trở mảnh. Các nút được đánh số từ \(0\) đến \(N-1\), các điện trở được đánh số từ \(0\) đến \(M-1\). Mỗi nút có thể được đặt ở một trong hai trạng thái: điện áp cao hoặc điện áp thấp. Điện trở \(i\) nối từ nút \(A_i\) đến một nút khác \(B_i\). Dòng điện chạy qua điện trở này khi và chỉ khi \(A_i\) ở điện áp cao và \(B_i\) ở điện áp thấp; dòng điện chỉ có thể chạy theo chiều đó. Giữa hai nút bất kỳ có nhiều nhất một điện trở, không phân biệt chiều nối.

Bạn là nhà nghiên cứu tại JOI và sẽ tiến hành thí nghiệm với mạch này. Các điện trở quá mảnh nên bạn không thể nhìn thấy chúng nối những cặp nút nào. Tuy nhiên, có một manh mối: khi đặt điện áp cho các nút, nhiệt độ của mạch tăng theo số điện trở có dòng điện chạy qua. Bạn quyết định chạm vào mạch để so sánh nhiệt độ. Bạn không thể đo nhiệt độ chính xác, nhưng có thể thử hai cách đặt điện áp và so sánh nhiệt độ của mạch giữa hai cách đó. Mỗi lần so sánh chỉ cho biết một trong ba kết quả:

• Số điện trở có dòng điện chạy qua trong cách đặt thứ nhất lớn hơn.
• Số điện trở có dòng điện chạy qua trong hai cách đặt bằng nhau.
• Số điện trở có dòng điện chạy qua trong cách đặt thứ hai lớn hơn.

Mục tiêu là dùng các phép so sánh này để xác định toàn bộ điện trở, tức là tất cả các cặp có thứ tự \((a,b)\) sao cho có điện trở từ nút \(a\) đến nút \(b\). Bạn được biết trước \(N\) và \(M\), cũng như các điều kiện mỗi điện trở nối hai nút khác nhau và giữa mỗi cặp nút có nhiều nhất một điện trở, không phân biệt chiều. Chỉ dựa vào những điều kiện đó và thông tin từ các phép so sánh nhiệt độ, hãy xác định toàn bộ các cặp \((a,b)\).

Tùy cấu trúc mạch, có thể không xác định duy nhất các điện trở dù thực hiện bao nhiêu phép so sánh đi nữa. Khi đó, bạn phải báo rằng không thể xác định duy nhất mạch. Đây là tính không thể xác định vốn có của mạch, không phải chỉ do hết lượt truy vấn.

Để tránh làm hỏng điện trở, bạn được so sánh nhiệt độ tối đa \(30000\) lần. Nhân tiện, phát minh mà JOI đang chế tạo bằng mạch điện này là bí mật ngay cả trong công ty; chỉ chủ tịch biết nó là gì.

Cho số nút và số điện trở, hãy viết chương trình xác định các điện trở hoặc báo rằng không thể xác định duy nhất, bằng không quá \(30000\) phép so sánh nhiệt độ.

Giao diện

Đây là bài tương tác qua hàm. Nộp mã C++ có #include "voltage.h" và cài đặt hàm sau, không viết main:

bool solve(int N, int M);

• Hàm được gọi đúng một lần trong mỗi lần chạy, với \(N\) là số nút và \(M\) là số điện trở. Chương trình thí sinh chạy trong một tiến trình.
• Trả về false nếu không thể xác định duy nhất các điện trở dù thực hiện bao nhiêu phép so sánh nhiệt độ đi nữa; ngược lại, trả về true.
• Trả về true khi không thể xác định duy nhất bị chấm Wrong Answer [1].
• Trả về false khi có thể xác định mạch từ các phép so sánh nhiệt độ bị chấm Wrong Answer [2].

Chương trình được gọi hai hàm sau do hệ thống cung cấp:

int query(std::vector<int> x, std::vector<int> y);
void answer(int a, int b);

Hàm query thực hiện hai cách đặt điện áp và so sánh nhiệt độ:

• x mô tả cách đặt thứ nhất, y mô tả cách đặt thứ hai. Mỗi mảng phải có độ dài \(N\) và chỉ gồm \(0\) hoặc \(1\).
• Với \(0\le k<N\), x[k] = 1 đặt nút \(k\) ở điện áp cao trong cách thứ nhất, còn x[k] = 0 đặt nút đó ở điện áp thấp. y[k] có ý nghĩa tương tự cho cách thứ hai.
• Giá trị trả về là -1 nếu cách thứ nhất có nhiều điện trở dẫn điện hơn, 0 nếu bằng nhau, hoặc 1 nếu cách thứ hai có nhiều điện trở dẫn điện hơn.
• Nếu độ dài x khác \(N\): Wrong Answer [3].
• Nếu x chứa giá trị khác \(0,1\): Wrong Answer [4].
• Nếu độ dài y khác \(N\): Wrong Answer [5].
• Nếu y chứa giá trị khác \(0,1\): Wrong Answer [6].
• Không được gọi hàm quá \(30000\) lần; vi phạm bị chấm Wrong Answer [7].

Hàm answer báo một điện trở đã xác định, có chiều từ nút \(a\) đến nút \(b\):

• Phải có \(0\le a,b<N\); nếu không, bị chấm Wrong Answer [8].
• Không được gọi hàm nhiều lần với cùng cặp \((a,b)\); vi phạm bị chấm Wrong Answer [9].
• Không được gọi hàm quá \(M\) lần; vi phạm bị chấm Wrong Answer [10].
• Khi solve trả về true, phải đã gọi answer đúng \(M\) lần; nếu không, bị chấm Wrong Answer [11].
• Khi solve trả về true, mỗi cặp \((a,b)\) đã báo phải thực sự tương ứng với một điện trở từ \(a\) đến \(b\); nếu không, bị chấm Wrong Answer [12].

Bạn có thể cài đặt các hàm phụ hoặc khai báo biến toàn cục dùng nội bộ. Chương trình nộp không được dùng đầu vào/đầu ra chuẩn hay tương tác với tệp khác. Có thể dùng luồng lỗi chuẩn để gỡ lỗi.

Hệ thống chấm không thích nghi: đáp án được cố định từ trước khi bắt đầu tương tác.

Chương trình chấm mẫu

Bộ tệp công khai gồm voltage.h, mã khung voltage.cpp, chương trình chấm mẫu grader.cpp và compile.sh. Chương trình chấm mẫu khác với hệ thống chấm chính thức. Để thử chương trình, đặt grader.cpp, voltage.cpp và voltage.h trong cùng thư mục rồi biên dịch bằng lệnh:

g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp

Hoặc chạy sh compile.sh. Tệp thực thi được tạo có tên grader.

Chương trình chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Đầu vào có dạng:

N M
A_0 B_0
A_1 B_1
...
A_{M-1} B_{M-1}

Nếu phát hiện một lỗi từ Wrong Answer [3] đến Wrong Answer [12], chương trình chấm mẫu in loại lỗi, chẳng hạn Wrong Answer [5], và kết thúc ngay. Nếu đồng thời vi phạm nhiều điều kiện, chỉ một lỗi được hiển thị.

Nếu không phát hiện các lỗi đó, chương trình chấm mẫu in số lần gọi query và giá trị trả về của solve, chẳng hạn Accepted: 30 true.

Chương trình chấm mẫu không kiểm tra Wrong Answer [1] và Wrong Answer [2], tức là không kiểm tra giá trị true/false mà solve trả về có đúng với khả năng xác định duy nhất mạch hay không. Vì vậy, thông báo Accepted từ chương trình chấm mẫu không đảm bảo chương trình đúng.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của những hàm được mô tả ở trên, không đọc đầu vào chuẩn.

Dữ liệu ra

Bài nộp không ghi đầu ra chuẩn. Kết quả được trả qua giá trị trả về của các hàm được mô tả ở trên.

Ràng buộc

• \(2\le N\le500\).
• \(1\le M\le1000\).
• \(0\le A_i,B_i\le N-1\) với mọi \(0\le i\le M-1\).
• \(A_i\ne B_i\) với mọi \(0\le i\le M-1\).
• Với mọi \(0\le i<j\le M-1\), \((A_i,B_i)\ne(A_j,B_j)\) và \((A_i,B_i)\ne(B_j,A_j)\).
• \(N,M,A_i,B_i\) đều là số nguyên.

Phân nhóm

1. \(10\) điểm: \(N\le100\), \(M=N-1\), \(B_i=A_{i+1}\) với mọi \(0\le i\le N-3\); \(N\) giá trị \(A_0,A_1,\ldots,A_{N-2},B_{N-2}\) đôi một khác nhau.
2. \(12\) điểm: \(M=N-1\), \(B_i=A_{i+1}\) với mọi \(0\le i\le N-3\); \(N\) giá trị \(A_0,A_1,\ldots,A_{N-2},B_{N-2}\) đôi một khác nhau.
3. \(27\) điểm: \(N\le100\) và \(A_i\ne A_j\) với mọi \(0\le i<j\le M-1\).
4. \(18\) điểm: \(A_i\ne A_j\) với mọi \(0\le i<j\le M-1\).
5. \(17\) điểm: \(N\le100\).
6. \(16\) điểm: Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Dưới đây là đầu vào cho chương trình chấm mẫu và một chuỗi lời gọi hàm tương ứng.

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

5 6
0 2
2 1
0 3
3 2
3 4
4 1

Tương tác

Giải thích

Trong lần gọi query đầu tiên:

• Cách đặt thứ nhất: nút \(0,1\) ở điện áp thấp; nút \(2,3,4\) ở điện áp cao. Dòng điện chạy qua các điện trở \(1,5\).
• Cách đặt thứ hai: nút \(3,4\) ở điện áp thấp; nút \(0,1,2\) ở điện áp cao. Dòng điện chạy qua điện trở \(2\).

Số điện trở dẫn điện trong cách thứ nhất lớn hơn nên hàm trả về \(-1\).

Ví dụ này thỏa mãn các ràng buộc của nhóm \(5,6\).

Trong các tệp ví dụ được đề gốc nhắc đến, sample-01-in.txt tương ứng với ví dụ trên; sample-02-in.txt thỏa mãn ràng buộc của tất cả các nhóm và sample-03-in.txt thỏa mãn các ràng buộc của nhóm \(3,4,5,6\).

Nguồn

JOI 2025/2026 - Chung kết, Cuộc thi 4, bài Voltage 2. Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.