JOI 2008 Representative Selection - Ngày 1

Ủy ban Olympic Tin học Nhật Bản có cơ cấu cấp trên và cấp dưới rất nghiêm ngặt. Có đúng một chủ tịch; mỗi người khác có đúng một cấp trên trực tiếp. Vì bảo mật, mỗi người chỉ biết cấp trên trực tiếp và các cấp dưới trực tiếp của mình. Không được liên lạc bằng phương tiện điện tử hoặc công cộng, nên những người không biết nhau phải truyền thông tin qua những người quen biết trực tiếp.

Mỗi thành viên có một chỉ số nhiệt tình, có thể âm. Ủy ban muốn chọn ít nhất một người cho một dự án tuyệt mật. Mức độ thành công được đánh giá bằng tổng chỉ số nhiệt tình của những người được chọn. Bất kỳ hai người trong dự án phải liên lạc được với nhau mà không nhờ người ngoài dự án chuyển tiếp.

Biết cấp trên và chỉ số nhiệt tình của mỗi người, hãy tìm tổng chỉ số nhiệt tình lớn nhất của một nhóm hợp lệ.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa số thành viên \(n\), với \(1 \le n \le 100000\).

Dòng thứ \(i+1\) chứa \(s_i,a_i\), với \(0 \le s_i < i\) và \(-100 \le a_i \le 100\). Người \(i\) có cấp trên là người \(s_i\) và chỉ số nhiệt tình \(a_i\). Giá trị \(s_i=0\) chỉ chủ tịch. Cấp trên luôn có số thứ tự nhỏ hơn cấp dưới.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là tổng chỉ số nhiệt tình lớn nhất.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm; tổng cộng \(100\) điểm.

Ví dụ

5
0 10
1 5
2 -8
1 -15
4 3

15

Có \(N\) tờ giấy hình chữ nhật, đánh số từ \(1\) đến \(N\), có màu đôi một khác nhau. Một chiếc bàn hình chữ nhật có màu khác tất cả các tờ giấy. Người ta lần lượt đặt cả \(N\) tờ giấy lên bàn theo các quy tắc:

• Các cạnh tờ giấy song song với các cạnh bàn.
• Tờ giấy mới luôn nằm trên những tờ đã đặt, không luồn xuống dưới.
• Độ dài các cạnh bàn và giấy là số nguyên. Khoảng cách từ giấy đến các cạnh bàn cũng là số nguyên.

Sau khi đặt xong, người ta chụp ảnh từ trên xuống. Biết bức ảnh, hãy đưa ra một thứ tự đặt giấy phù hợp với ảnh.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(N,W,H\): số tờ giấy, chiều rộng và chiều cao bàn, với \(1 \le N \le 1000\), \(1 \le W,H \le 100\).

Chia bàn thành \(W \cdot H\) ô vuông đơn vị. Dòng thứ \(i+1\) chứa \(W\) số \(C_{i,1},\ldots,C_{i,W}\), biểu thị màu ô ở hàng \(i\) từ trên xuống, cột \(j\) từ trái sang. \(C_{i,j}=0\) nghĩa là thấy màu bàn; \(C_{i,j}>0\) nghĩa là thấy màu của tờ giấy mang số đó, với \(0 \le C_{i,j} \le N\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa \(N\) số nguyên, cách nhau bởi dấu cách, biểu thị thứ tự các tờ giấy từ tờ đặt đầu tiên đến tờ đặt cuối cùng. Nếu có nhiều thứ tự phù hợp, được phép ghi bất kỳ thứ tự nào.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm.

Ví dụ

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

3 4 1 2

Nước JOI có \(n\) thành phố \(P_1,\ldots,P_n\), với \(P_i\) ở tọa độ \((x_i,y_i)\). Các tọa độ đôi một khác nhau. \(P_1\) là thủ đô JOI.

Một chủng cúm đặc biệt có các đặc điểm sau:

1. Mỗi khi dịch bắt đầu ở một thành phố, dịch kéo dài đúng \(m\) ngày, rồi kết thúc sau \(m\) ngày.
2. Thành phố đã trải qua dịch có miễn dịch, nên dịch không bao giờ xảy ra lần thứ hai tại đó.
3. Nếu dịch bắt đầu ở thành phố \(P_i\), thì ngày hôm sau dịch bắt đầu tại mọi thành phố chưa từng có dịch và cách \(P_i\) không quá \(d\).
4. Dịch không lan qua con đường nào khác.

Khoảng cách giữa hai thành phố là khoảng cách Euclid:

Với mỗi thành phố, có không quá \(10\) thành phố khác nằm cách nó không quá \(d\).

Ngày đầu tiên, dịch bắt đầu tại \(P_1\) và chưa xảy ra ở bất kỳ thành phố nào khác. Hãy dự đoán số thành phố đang có dịch sau \(k\) ngày kể từ thời điểm đó để bố trí vắc-xin điều trị.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Bốn dòng đầu lần lượt chứa \(n,m,d,k\), với \(1 \le n \le 100000\), \(1 \le m \le 100\), \(1 \le d \le 25\), \(1 \le k \le 100\).

\(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i,y_i\), với \(0 \le x_i,y_i < 1000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số thành phố đang có dịch sau \(k\) ngày kể từ khi dịch bắt đầu tại \(P_1\).

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm. \(20\%\) số điểm ứng với \(n \le 1000\), \(k \le 50\), \(0 \le x_i,y_i < 100\). Một phần \(30\%\) khác ứng với \(n \le 10000\), \(0 \le x_i,y_i < 1000\).

Ví dụ

9
2
2
3
1 3
3 3
2 2
3 1
0 0
0 3
0 5
3 5
5 5

4