BOI 2013 - Ngày 1

Một “máy thả bóng” có dạng cây có gốc, gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\). Mỗi đỉnh hoặc rỗng, hoặc chứa đúng một quả bóng. Ban đầu mọi đỉnh đều rỗng. Máy thực hiện hai loại thao tác:

1. Thêm \(k\) quả bóng: Lần lượt đặt từng quả bóng vào đỉnh gốc. Chừng nào đỉnh đang chứa quả bóng còn có một đỉnh con rỗng, quả bóng sẽ lăn xuống. Nếu có nhiều đỉnh con rỗng, quả bóng chọn đỉnh con có cây con chứa đỉnh mang số nhỏ nhất. Quy tắc này được áp dụng lại ở mỗi tầng mà quả bóng đi qua. Chẳng hạn, khi thêm hai quả bóng vào máy dưới đây, chúng dừng ở các đỉnh \(1\) và \(3\). Quả thứ nhất đi từ \(4\) xuống \(3\) vì cây con của \(3\) chứa đỉnh \(1\), rồi tiếp tục xuống \(1\). Quả thứ hai cũng đi từ \(4\) xuống \(3\) và dừng lại.

   

2. Lấy một quả bóng khỏi đỉnh được chỉ định: Đỉnh đó trở thành rỗng và các quả bóng ở phía trên, nếu có, lăn xuống. Khi cha của một đỉnh rỗng có bóng, quả bóng ở đỉnh cha sẽ lăn xuống đỉnh rỗng đó. Nếu lần lượt lấy bóng khỏi các đỉnh \(5\), \(7\), \(8\) trong máy dưới đây, các đỉnh \(1\), \(2\), \(3\) sẽ trở thành rỗng.

   

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(Q\), lần lượt là số đỉnh và số thao tác.

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số hiệu cha của đỉnh \(i\), hoặc \(0\) nếu \(i\) là gốc.

Mỗi dòng trong \(Q\) dòng tiếp theo mô tả một thao tác:

• 1 k: thêm \(k\) quả bóng vào máy.
• 2 x: lấy một quả bóng khỏi đỉnh \(x\).

Mọi thao tác đều hợp lệ: số bóng được thêm không vượt quá số đỉnh rỗng, và thao tác lấy bóng luôn chỉ đến một đỉnh đang có bóng.

Dữ liệu ra

Với mỗi thao tác loại \(1\), in số hiệu đỉnh mà quả bóng được thêm cuối cùng dừng lại. Với mỗi thao tác loại \(2\), in số quả bóng đã lăn xuống sau khi lấy quả bóng được chỉ định. Mỗi kết quả nằm trên một dòng riêng.

Ràng buộc

• \(1 \le N,Q \le 100\,000\).
• \(1 \le k \le N\) và \(1 \le x \le N\), đồng thời các thao tác thỏa điều kiện hợp lệ nêu trên.

Phân nhóm

• Nhóm \(25\) điểm: mỗi đỉnh có đúng \(0\) hoặc \(2\) đỉnh con; mọi đỉnh không có con đều cách gốc một khoảng bằng nhau.
• Nhóm \(30\) điểm: các thao tác được chọn sao cho không có quả bóng nào lăn xuống sau bất kỳ thao tác loại \(2\) nào.
• Nhóm \(40\) điểm: có đúng một thao tác loại \(1\), và đó là thao tác đầu tiên.
• \(5\) điểm còn lại: không có ràng buộc bổ sung.

Ba tập dữ liệu tương ứng với các nhóm \(25\), \(30\) và \(40\) điểm đôi một không giao nhau.

Ví dụ

8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8

1
3
2
2

Một xâu được gọi là đối xứng nếu đọc từ trái sang phải hay từ phải sang trái đều được cùng một xâu. Một số nguyên được gọi là không chứa đối xứng nếu biểu diễn thập phân thông thường của nó không có xâu con liên tiếp đối xứng dài hơn \(1\) ký tự. Chẳng hạn, \(16276\) không chứa đối xứng, còn \(17276\) chứa xâu đối xứng \(727\).

Hãy đếm các số không chứa đối xứng trong đoạn từ \(a\) đến \(b\), kể cả hai đầu mút. Biểu diễn của một số không có chữ số \(0\) thừa ở đầu; riêng số \(0\) được biểu diễn bằng một chữ số \(0\) và cũng được tính.

Dữ liệu vào

Hai số nguyên \(a\) và \(b\).

Dữ liệu ra

Một số nguyên là số lượng số không chứa đối xứng trong đoạn \([a,b]\).

Ràng buộc

• \(0 \le a \le b \le 10^{18}\).

Phân nhóm

• \(25\) điểm: \(b-a \le 100\,000\).
• \(75\) điểm còn lại: không có ràng buộc bổ sung.

Ví dụ

123 321

153

123456789 987654321

167386971

Thành phố Hotham có \(N\) hồ chứa nước, nối với nhau bởi \(M\) đường ống. Mạng lưới liên thông: từ bất kỳ hồ nào cũng có thể đi đến bất kỳ hồ khác qua các đường ống. Mỗi ống nối hai hồ khác nhau và giữa hai hồ có nhiều nhất một ống.

Tên tội phạm Jester đang rút nước khỏi một số ống và bơm nước vào một số ống khác. Lượng nước hắn rút hoặc bơm tại mỗi ống luôn là một số nguyên chẵn mét khối mỗi giây. Nếu hắn rút \(2d\) mét khối mỗi giây khỏi ống nối \(u\) và \(v\), mỗi hồ mất \(d\) mét khối mỗi giây. Nếu hắn bơm \(2p\) mét khối mỗi giây vào ống đó, mỗi hồ nhận thêm \(p\) mét khối mỗi giây.

Các cảm biến chỉ đo được độ biến thiên ròng \(c_i\) của mỗi hồ, bằng tổng lượng nhận thêm trừ tổng lượng mất đi từ các ống kề với hồ đó. Thị trưởng muốn biết liệu các số đo này có xác định duy nhất lượng nước được bơm vào hoặc rút khỏi từng ống hay không. Nếu có, hãy tìm các lượng đó. Các ống không nhất thiết có cùng lượng nước bị tác động.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(M\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên \(c_i\), là độ biến thiên ròng của hồ \(i\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(u_i,v_i\), cho biết ống thứ \(i\) nối hai hồ này. Các hồ được đánh số từ \(1\) đến \(N\). Dữ liệu bảo đảm tồn tại ít nhất một cách bơm và rút nước thỏa mãn mọi số đo.

Dữ liệu ra

Nếu không thể xác định duy nhất kế hoạch của Jester, in một dòng chứa \(0\).

Nếu có duy nhất một kế hoạch, in \(M\) dòng. Dòng thứ \(i\) chứa số nguyên \(x_i\), là toàn bộ lượng nước Jester tác động lên ống thứ \(i\) trong một giây: dương nếu bơm vào, âm nếu rút ra và bằng \(0\) nếu không tác động. Mỗi hồ ở hai đầu ống nhận độ biến thiên \(x_i/2\) từ ống này; vì thế

Ràng buộc

• \(1 \le N \le 100\,000\), \(1 \le M \le 500\,000\).
• \(1 \le u_i,v_i \le N\), \(u_i \ne v_i\); đồ thị đơn và liên thông.
• \(-10^9 \le c_i \le 10^9\).
• Nếu kế hoạch là duy nhất thì \(-10^9 \le x_i \le 10^9\).

Phân nhóm

• \(30\) điểm: mạng lưới là một cây.
• \(70\) điểm còn lại: không có ràng buộc bổ sung.

Ví dụ

4 3
-1
1
-3
1
1 2
1 3
1 4

2
-6
2

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

0