Đây là một bài toán giao tiếp.
Nhà khoa học vĩ đại 欣 chuẩn bị xây dựng trí tuệ nhân tạo mạnh 隆 để thống trị thế giới. Sau khi đưa một số bài toán thi lập trình của Việt Nam vào làm tập huấn luyện, cô phát hiện 隆 tự tạo ra một bài toán mới và đưa ra một lời giải. Đồng thời, 隆 còn quy giảm 30% dữ liệu vào trong tập kiểm thử về bài toán này. 欣 vội chép lại bài toán như sau: Cho một cây có gốc, bạn cần hỗ trợ hai thao tác:
- Truy vấn tổng các phần tử trên một đường đi trong cây.
- Đổi cha của một đỉnh thành một đỉnh khác.
“Bài toán này đâu có ghê gớm, tại sao lại giải được 30% bài trong tập kiểm thử?” 欣 thầm nghĩ. Trước khi đóng trang kết quả huấn luyện, 欣 chợt phát hiện rằng trong bài toán 隆 đưa ra, chi phí gộp thông tin không phải là $O(1)$. 欣 trầm ngâm suy nghĩ và nhận ra chính mình cũng không biết giải bài này. Để biết bài này khó đến mức nào, 欣 đặt nó trước mặt bạn.
Mô tả bài toán
Bạn cần duy trì một cây có gốc tại $1$, gồm $n$ đỉnh. Ban đầu, với mọi $2 \le i \le n$, đỉnh $i$ có cha là $p_i$, bảo đảm $p_i \lt i$.
Ban đầu bạn có $n$ tập hợp $\{1\},\{2\},\cdots,\{n\} $. Với hai tập hợp bất kỳ $A$ và $B$, nếu $A \cap B=\varnothing$, bạn có thể thực hiện một thao tác với chi phí $|A|+|B|$ để thu được tập hợp $A \cup B$.
Sau đó có $q$ thao tác. Mỗi thao tác thuộc một trong hai loại:
0 a b: Gọi $S$ là tập các đỉnh trên đường đi từ $a$ đến $b$ trong cây. Bạn cần biểu diễn $S$ thành $\cup_{i=1}^{k}A_i$, trong đó $A_i$ phải là tập hợp bạn đã thu được và $\forall i \neq j,A_i \cap A_j=\varnothing$. Chi phí trả lời một truy vấn bằng $(A_1,A_2,\cdots,A_k) $ là $k$.1 a b: Đổi cha của đỉnh $a$ thành $b$. Bảo đảm $a \gt 1$ và sau khi thay đổi, $n$ đỉnh vẫn tạo thành một cây, nhưng không bảo đảm $a \gt b$. Trong thao tác này, bạn có thể tạo thêm một số tập hợp để phục vụ các truy vấn sau.
Gọi tổng chi phí trong suốt quá trình chạy chương trình là $C_1$, và chi phí lớn nhất của một thao tác là $C_2$. Mỗi nhiệm vụ con sẽ được chấm điểm theo một cách nhất định dựa trên giá trị $C_1,C_2$.
Chi tiết cài đặt
Hãy bảo đảm đầu chương trình có #include "long.h".
Tệp tiêu đề định nghĩa kiểu dữ liệu infoset để lưu các tập hợp bạn thu được.
Kiểu này có hàm thành viên size() cho biết kích thước tập hợp. Tệp tiêu đề còn cung cấp hằng emptyset biểu diễn tập rỗng.
Ngoài ra, bạn có thể gọi các hàm sau:
infoset merge(const infoset&A,const infoset&B);
- Tạo một tập hợp mới $A \cup B$ với một chi phí nhất định.
- Lưu ý rằng bạn có thể tạo lại cùng một tập hợp nhiều lần, và chi phí phải được tính cho từng lần.
void report(infoset A);
- Bạn chỉ được gọi hàm này trong thao tác truy vấn; hàm biểu thị việc thêm tập hợp $A$ vào phép hợp cuối cùng với chi phí $1$.
Bạn không cần và cũng không được cài đặt hàm chính. Bạn cần cài đặt các hàm sau:
void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);
- Bạn có thể tiền xử lý một số thông tin trước khi $q$ thao tác bắt đầu.
- Chi phí trong hàm này không được tính vào chi phí lớn nhất của một thao tác, nhưng được tính vào tổng chi phí trong suốt quá trình chạy chương trình.
idlà số hiệu nhiệm vụ con,nlà tổng số đỉnh,qlà tổng số thao tác.dadcó kích thước $n-1$;dad[i]là cha của đỉnh $i+2$ tại thời điểm ban đầu.vecó kích thước $n$;ve[i]là tập hợp ban đầu $\{i+1\}$.
void modify(int x,int y);
- Thực hiện một thao tác thay đổi, đặt cha của đỉnh $x$ thành đỉnh $y$.
void ask(int x,int y);
- Thực hiện một thao tác truy vấn thông tin trên đường đi từ $x$ đến $y$ trong cây.
- Bạn cần gọi
reportmột số lần để trả lời truy vấn. Khi truy vấn kết thúc, thư viện giao tiếp sẽ kiểm tra tất cả các tập hợp $A$ bạn báo cáo có thỏa mãn điều kiện hay không.
Khi chấm bài, thư viện giao tiếp sẽ gọi init một lần, sau đó gọi modify và ask tổng cộng $q$ lần.
Bài toán bảo đảm hình dạng cây và các thao tác thực hiện đã được xác định hoàn toàn trước khi giao tiếp bắt đầu, không được xây dựng động dựa trên quá trình giao tiếp với chương trình của bạn. Do đó, các thao tác giao tiếp trong bài đều có tính xác định, và bạn không cần quan tâm cách cài đặt cụ thể của chúng trong thư viện giao tiếp.
Khi chấm bài, thư viện giao tiếp dùng cách cài đặt đặc biệt: mỗi biến kiểu infoset luôn chiếm $8$ byte bộ nhớ. Hãy bảo đảm không có quá nhiều biến kiểu infoset cùng tồn tại khi chương trình chạy.
Bảo đảm rằng trong giới hạn số lần gọi, thời gian chạy của thư viện giao tiếp không vượt quá 2 giây; bộ nhớ do chính thư viện giao tiếp sử dụng không vượt quá 16 MB.
Cách kiểm thử chương trình
Tệp grader.cpp được phát kèm là một cài đặt tham khảo của thư viện giao tiếp do chúng tôi cung cấp. Cài đặt thư viện giao tiếp dùng khi chấm chính thức khác với cài đặt tham khảo này, vì vậy lời giải của thí sinh không được phụ thuộc vào cách cài đặt thư viện giao tiếp.
Bạn cần dùng lệnh sau để biên dịch thành chương trình thực thi:
g++ grader.cpp long.cpp -o long -static -O2 -std=c++14
Đối với chương trình thực thi đã biên dịch:
Chương trình đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:
- Dòng đầu chứa một số nguyên $id$, là số hiệu nhiệm vụ con.
- Dòng thứ hai chứa hai số nguyên $n,q$, là tổng số đỉnh và tổng số thao tác.
- Dòng thứ ba chứa $n-1$ số nguyên, lần lượt là số hiệu cha của các đỉnh từ $2$ đến $n$.
- Tiếp theo là $q$ dòng, mỗi dòng chứa ba số nguyên $op,x,y$ mô tả một thao tác. $op=0$ biểu thị thao tác truy vấn, $op=1$ biểu thị thao tác thay đổi.
- Sau khi đọc xong, thư viện giao tiếp sẽ gọi hàm
initđúng một lần và gọimodifyhoặcask$q$ lần, dùng dữ liệu vào để kiểm thử các hàm của bạn. Khi chạy bình thường, chương trình sẽ xuất một số dòng, mỗi dòng chứa một số số biểu diễn câu trả lời bạn đưa ra cho từng thao tác truy vấn; dòng cuối chứa hai số nguyên $W_1,W_2$, lần lượt là tổng chi phí chương trình và chi phí lớn nhất của một thao tác.
Các tệp phát kèm gồm bốn bộ tệp ví dụ, trong đó bộ thứ tư thỏa mãn tính chất đặc biệt của nhiệm vụ con 2. Khi kiểm thử ví dụ, hãy bỏ qua việc so sánh dòng cuối của tệp đầu ra, vì dòng cuối thư viện giao tiếp xuất ra là chi phí chương trình, không phải kết quả truy vấn.
Nhiệm vụ con
Trước hết, bài này chịu các giới hạn giống bài truyền thống. Ví dụ, lỗi biên dịch khiến toàn bộ bài được $0$ điểm; lỗi chạy, vượt giới hạn thời gian hoặc bộ nhớ khiến trường hợp kiểm thử tương ứng được $0$ điểm, v.v. Bạn chỉ được truy cập các biến do mình định nghĩa hoặc do thư viện giao tiếp cung cấp cùng vùng nhớ tương ứng của chúng. Cố truy cập các vùng nhớ khác có thể gây lỗi biên dịch hoặc lỗi chạy.
Ngoài các điều kiện trên, trong một trường hợp kiểm thử, nếu chương trình gọi hàm không hợp lệ, không kết thúc bình thường hoặc trả lời sai một truy vấn, trường hợp đó được $0$ điểm. Nếu không, có hai cách tính điểm dựa trên chi phí chương trình:
- Cách chấm 1: Nếu $W_1 \gt 6 \cdot 10^8$, trường hợp kiểm thử được $0$ điểm; nếu không, điểm là $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10}$ nhân với điểm của nhiệm vụ con chứa trường hợp kiểm thử đó.
- Cách chấm 2: Nếu $W_2 \gt 2 \cdot 10^4$, trường hợp kiểm thử được $0$ điểm; nếu không, điểm là $\frac{5000}{max(W_2,5000)}$ nhân với điểm của nhiệm vụ con chứa trường hợp kiểm thử đó.
Các nhiệm vụ con khác nhau dùng các cách chấm khác nhau. Điểm của một nhiệm vụ con là giá trị nhỏ nhất trong các điểm của tất cả trường hợp kiểm thử thuộc nhiệm vụ con đó.
Giới hạn
Bảo đảm với mọi trường hợp kiểm thử, $1 \le n,q \le 10^5$.
| Số hiệu nhiệm vụ con | $n,q \le$ | Tính chất đặc biệt | Cách chấm | Điểm |
|---|---|---|---|---|
| $1$ | $100$ | Không | .h=2 1 | $10$ |
| $2$ | .h=4 $10^5$ | .h=2 Có | $20$ | |
| $3$ | 2 | $20$ | ||
| $4$ | .h=2 Không | 1 | $30$ | |
| $5$ | 2 | $20$ |
Tính chất đặc biệt: Tại mọi thời điểm, mọi đỉnh trừ đỉnh $1$ đều có nhiều nhất một con.
Lời kết
欣 thấy bạn vẫn chưa giải được bài sau năm giờ, nên rất hài lòng với năng lực của 隆. Thế nhưng sáng hôm sau thức dậy, 欣 chợt phát hiện chứng minh độ phức tạp trong cách làm của 隆 là sai.