APIO 2012

Trong một môn phái ninja, các ninja được cử đi làm nhiệm vụ cho khách hàng và nhận thù lao theo công việc. Có đúng một ninja là Trưởng môn. Mỗi ninja khác có đúng một cấp trên. Để bảo mật và khuyến khích năng lực lãnh đạo, mọi chỉ thị công việc chỉ được truyền từ cấp trên xuống cấp dưới, có thể qua nhiều người trung gian.

Bạn cần chọn một số ninja để cử đi làm nhiệm vụ. Ninja được cử đi phải được trả mức lương cố định của họ, và tổng lương không được vượt quá ngân sách. Bạn cũng phải chọn một ninja làm quản lý sao cho người này có thể truyền chỉ thị tới mọi ninja được cử đi. Các ninja không được cử đi vẫn có thể làm trung gian truyền chỉ thị. Quản lý có thể được cử đi hoặc không; nếu không được cử đi thì không phải trả lương cho người đó.

Mức độ hài lòng của khách hàng bằng số ninja được cử đi nhân với chỉ số lãnh đạo của quản lý. Hãy tìm mức độ hài lòng lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N, M\): số ninja và ngân sách.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(B_i, C_i, L_i\): cấp trên, mức lương và chỉ số lãnh đạo của ninja \(i\). Nếu \(B_i=0\) thì ninja \(i\) là Trưởng môn.

Luôn có \(B_i<i\), do đó số hiệu cấp trên của một ninja luôn nhỏ hơn số hiệu của ninja đó.

Dữ liệu ra

In ra mức độ hài lòng lớn nhất có thể đạt được.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le M\le 1\,000\,000\,000\).
• \(0\le B_i<i\).
• \(1\le C_i\le M\).
• \(1\le L_i\le 1\,000\,000\,000\).

Ví dụ

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

6

Giải thích

Chọn ninja \(1\) làm quản lý và cử ninja \(3,4\) đi làm nhiệm vụ. Tổng lương là \(4\), không vượt quá ngân sách. Có \(2\) ninja được cử đi và chỉ số lãnh đạo của quản lý là \(3\), nên mức độ hài lòng là \(2\times3=6\). Đây là giá trị lớn nhất.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2012, bài Dispatching.

Vương quốc APIO đang bị ninja tấn công. Trước lâu đài có một hàng gồm \(N\) bụi cây, đánh số từ \(1\) đến \(N\). Có đúng \(K\) ninja ẩn trong đúng \(K\) bụi cây khác nhau.

Có \(M\) lính canh. Lính canh \(i\) quan sát đoạn bụi cây từ \(A_i\) đến \(B_i\) và báo rằng trong đoạn mình quan sát có ninja hay không. Dựa trên tất cả báo cáo, bạn phải xác định những bụi cây mà chắc chắn có ninja ẩn nấp. Một bụi cây được xem là chắc chắn có ninja nếu nó có ninja trong mọi cách bố trí \(K\) ninja không mâu thuẫn với các báo cáo.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(N,K,M\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i,C_i\) với \(A_i\le B_i\) và \(C_i\in\{0,1\}\):
• \(C_i=0\): không có ninja nào trong các bụi từ \(A_i\) đến \(B_i\).
• \(C_i=1\): có ít nhất một ninja trong các bụi từ \(A_i\) đến \(B_i\).

Dữ liệu bảo đảm tồn tại ít nhất một cách bố trí ninja phù hợp với mọi báo cáo.

Dữ liệu ra

Nếu có bụi cây chắc chắn chứa ninja, in số hiệu các bụi đó theo thứ tự tăng dần, mỗi số trên một dòng. Nếu không có bụi nào như vậy, in -1.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le K\le N\).
• \(1\le M\le 100\,000\).

Ví dụ

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

3
5

5 1 1
1 5 1

-1

Giải thích

Trong ví dụ thứ nhất có hai cách bố trí phù hợp: ninja ở các bụi \(1,3,5\) hoặc ở các bụi \(2,3,5\). Vì bụi \(3\) và \(5\) có ninja trong cả hai cách nên phải in 3 và 5.

Trong ví dụ thứ hai, không có bụi cây nào chắc chắn chứa ninja.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2012, bài Guard.

Kunai là một loại vũ khí sắc nhọn của ninja có hình dáng giống dao. Có \(N\) ninja đứng trên một lưới ô vuông gồm \(W\) cột và \(H\) hàng. Mỗi ninja đứng tại tâm một ô và không có hai ninja đứng cùng ô. Mỗi người cầm một kunai và nhìn theo một trong bốn hướng: lên, xuống, trái hoặc phải. Tại thời điểm \(0\), tất cả ninja đồng thời ném kunai theo hướng mình đang nhìn.

Mỗi kunai bay thẳng với vận tốc \(1\). Nếu từ hai kunai trở lên đến cùng một vị trí tại cùng một thời điểm, tất cả chúng va chạm và biến mất. Có thể bỏ qua kích thước của kunai. Kunai tiếp tục bay theo hướng ban đầu với vận tốc không đổi cho tới khi va chạm.

Trong ba hình sau, mũi tên biểu diễn kunai và hướng bay. Mọi mũi tên nét đậm trong từng hình đều va chạm với nhau.

{{asset:apio12-kunai-collision-1}}

{{asset:apio12-kunai-collision-2}}

{{asset:apio12-kunai-collision-3}}

Ngược lại, trong mỗi hình dưới đây, các mũi tên nét đậm không va chạm với nhau. Ở hình thứ hai và thứ ba, mũi tên nét mảnh va chạm với một mũi tên nét đậm trước; vì kunai đã va chạm sẽ biến mất, hai mũi tên nét đậm không còn có thể va chạm.

{{asset:apio12-kunai-no-collision-1}}

{{asset:apio12-kunai-no-collision-2}}

{{asset:apio12-kunai-no-collision-3}}

Hãy đếm số ô của lưới \(W\times H\) mà ít nhất một kunai đi qua sau khi đã chờ đủ lâu.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(W,H\).
• Dòng thứ hai chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(X_i,Y_i,D_i\). Ninja \(i\) đứng ở cột thứ \(X_i\) tính từ trái sang và hàng thứ \(Y_i\) tính từ trên xuống. Không có hai ninja cùng vị trí.

Hướng được mã hóa như sau:

• \(D_i=0\): sang phải.
• \(D_i=1\): lên trên.
• \(D_i=2\): sang trái.
• \(D_i=3\): xuống dưới.

Dữ liệu ra

In số ô mà ít nhất một kunai đi qua.

Ràng buộc

• \(1\le N\le100\,000\).
• \(1\le W,H\le1\,000\,000\,000\).
• \(1\le X_i\le W\) và \(1\le Y_i\le H\).

Ví dụ

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

11

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

29

Giải thích

Trạng thái ví dụ thứ nhất tại thời điểm \(0\):

{{asset:apio12-kunai-sample-start}}

Tại thời điểm \(0.5\), kunai \(2\) và \(3\) va chạm rồi biến mất. Hình dưới là trạng thái tại thời điểm \(1\); các ô màu xám là những ô kunai đã đi qua.

{{asset:apio12-kunai-sample-t1}}

Tại thời điểm \(2\), kunai \(1\) và \(5\) va chạm rồi biến mất.

{{asset:apio12-kunai-sample-t2}}

Sau thời điểm \(2\) không còn va chạm nào trong lưới. Cuối cùng có \(11\) ô được kunai đi qua.

{{asset:apio12-kunai-sample-final}}

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2012, bài Kunai.