JOI 2025/2026 Final Stage - Competition 3

Đất nước JOI có dạng một tam giác đều cạnh \(L\), với ba đỉnh \(A\), \(B\), \(C\), trong đó \(L\) là số nguyên dương. Cạnh \(AB\) nằm theo hướng Đông - Tây: \(A\) là điểm cực Tây, \(B\) là điểm cực Đông, còn \(C\) là điểm cực Bắc của đất nước.

Đất nước được chia thành \(L^2\) vùng tam giác đều cạnh \(1\). Một điểm là đỉnh của một vùng được gọi là điểm lưới. Với các số nguyên \(x,y\) thỏa mãn \(0 \le y \le L\) và \(0 \le x \le L-y\), điểm lưới ở hàng thứ \(1+y\) tính từ phía Nam và là điểm thứ \(1+x\) tính từ phía Tây trong hàng đó được ký hiệu là \((x,y)\). Đặc biệt, \(A\), \(B\), \(C\) lần lượt là \((0,0)\), \((L,0)\), \((0,L)\). Hình dưới minh họa các vùng và điểm lưới khi \(L=5\).

Hình 1: Các vùng tam giác và điểm lưới khi \(L=5\).

Dự báo thời tiết cho \(N\) ngày tiếp theo đã được công bố. Trong ngày thứ \(i\), mưa sẽ rơi trên tam giác có ba đỉnh lưới \((X_i, Y_i)\), \((X_i + Z_i, Y_i)\) và \((X_i, Y_i + Z_i)\). Một vùng tam giác nhỏ được xem là có mưa trong ngày \(i\) nếu toàn bộ vùng đó nằm trong tam giác dự báo.

Để chuẩn bị ứng phó với thiên tai do mưa gây ra, với mỗi \(k = 1, 2, \ldots, K\), cần xác định số vùng được dự báo có mưa trong ít nhất \(k\) ngày. Cho kích thước đất nước, dự báo thời tiết và \(K\), hãy tính các số lượng này.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(L\), \(N\), \(K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(X_i\), \(Y_i\), \(Z_i\).

Dữ liệu ra

In ra \(K\) dòng. Dòng thứ \(k\) chứa số vùng được dự báo có mưa trong ít nhất \(k\) ngày.

Ràng buộc

• \(2 \le L \le 10^9\).
• \(2 \le N \le 200000\).
• \(1 \le K \le 5\).
• \(0 \le X_i, Y_i \le L\).
• \(1 \le Z_i \le L\).
• \(X_i + Y_i + Z_i \le L\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (4 điểm): \(N = 2\), \(K = 2\).
• Nhóm 2 (5 điểm): \(L \le 100\), \(N \le 100\).
• Nhóm 3 (5 điểm): \(L \le 1000\).
• Nhóm 4 (7 điểm): \(N \le 2000\).
• Nhóm 5 (10 điểm): \(X_i = 0\) với mọi \(1 \le i \le N\), \(K = 1\).
• Nhóm 6 (10 điểm): \(X_i = 0\) với mọi \(1 \le i \le N\).
• Nhóm 7 (23 điểm): \(K = 1\).
• Nhóm 8 (18 điểm): \(K \le 2\).
• Nhóm 9 (18 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 2 2
1 0 3
0 1 4

21
4

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

21
10
2
0
0

Nguồn

JOI 2025/2026 Final Stage, Competition 3, problem Triangular Rainfall. 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.

Cánh đồng rộng lớn của làng JOI được biểu diễn bằng mặt phẳng \(xy\) vô hạn, trong đó chiều dương của trục \(x\) là hướng Đông, chiều dương của trục \(y\) là hướng Bắc. Thị trưởng muốn đặt các con bù nhìn để bảo vệ cánh đồng khỏi kẻ địch. Mỗi bù nhìn bảo vệ một vùng tùy theo vị trí và hướng quay của nó. Có \(N\) kế hoạch đặt bù nhìn, được đánh số từ \(1\) đến \(N\). Thực hiện kế hoạch thứ \(i\) tốn chi phí \(C_i\) và đặt một bù nhìn theo ba số nguyên \(T_i, X_i, Y_i\) như sau:

• Nếu \(T_i = 1\), bù nhìn ở \((X_i, Y_i)\) quay về Tây và bảo vệ mọi điểm có \(x \le X_i\).
• Nếu \(T_i = 2\), bù nhìn ở \((X_i, Y_i)\) quay về Đông và bảo vệ mọi điểm có \(x \ge X_i\).
• Nếu \(T_i = 3\), bù nhìn ở \((X_i, Y_i)\) quay về Nam và bảo vệ mọi điểm có \(y \le Y_i\).
• Nếu \(T_i = 4\), bù nhìn ở \((X_i, Y_i)\) quay về Bắc và bảo vệ mọi điểm có \(y \ge Y_i\).

Hãy chọn một số kế hoạch sao cho mọi điểm trên mặt phẳng được bảo vệ bởi ít nhất \(K\) bù nhìn, và tổng chi phí là nhỏ nhất. Nếu không thể, in ra -1.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N\), \(K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(T_i\), \(X_i\), \(Y_i\), \(C_i\).

Dữ liệu ra

In ra chi phí nhỏ nhất cần thiết, hoặc -1 nếu không thể bảo vệ mọi điểm bởi ít nhất \(K\) bù nhìn.

Ràng buộc

• \(1 \le K \le N \le 200000\).
• \(T_i \in \{1,2,3,4\}\).
• \(0 \le X_i, Y_i \le 10^9\).
• Các cặp tọa độ \((X_i, Y_i)\) đôi một khác nhau.
• \(0 \le C_i \le 10^9\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (4 điểm): \(K = 1\).
• Nhóm 2 (6 điểm): \(K \le 2\).
• Nhóm 3 (11 điểm): \(N \le 500\), \(K \le 300\).
• Nhóm 4 (27 điểm): \(N \le 6000\).
• Nhóm 5 (19 điểm): \(N \le 75000\).
• Nhóm 6 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

7 1
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

99

7 3
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

-1

19 5
2 36 42 64
2 7 89 74
1 0 15 82
1 10 63 55
2 58 28 19
2 45 91 3
2 2 34 97
1 7 55 82
1 17 12 17
2 59 76 82
1 7 4 68
2 51 98 47
1 51 21 38
2 19 0 72
1 73 73 11
2 62 19 74
1 45 7 94
1 79 32 21
1 85 50 21

315

8 3
4 4 21 80
2 59 65 69
4 63 36 3
2 29 13 23
1 37 45 95
2 79 14 89
3 91 54 76
1 85 46 62

328

Nguồn

JOI 2025/2026 Final Stage, Competition 3, problem Scarecrows 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.

Đất nước IOI, nơi JOI-kun sinh sống, có \(N\) thị trấn được đánh số từ \(1\) đến \(N\), cùng \(N-1\) con đường được đánh số từ \(1\) đến \(N-1\). Đường thứ \(j\) nối hai thị trấn \(U_j\) và \(V_j\) theo cả hai chiều. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

Một cuộc hành trình sưu tập dấu sẽ được tổ chức. Mỗi thị trấn có một trạm đóng dấu; trạm ở thị trấn \(i\) được lắp đặt tại thời điểm \(T_i\).

JOI-kun quyết định tham gia. Cậu xuất phát từ một thị trấn ở thời điểm \(0\), với thể lực ban đầu \(D\). Khi ở thị trấn \(i\) tại thời điểm \(t\), cậu thực hiện các hành động sau:

1. Nếu trạm đóng dấu ở thị trấn hiện tại đã được lắp đặt, tức là \(T_i \le t\), cậu đóng dấu.
2. Cậu chọn kết thúc hành trình hoặc di chuyển sang thị trấn khác. Chỉ được chọn di chuyển nếu còn ít nhất \(1\) thể lực và có một thị trấn kề chưa từng ghé thăm.
3. Nếu chọn di chuyển, cậu chọn một thị trấn \(j\) chưa từng ghé thăm có đường nối trực tiếp với \(i\). Thể lực giảm \(1\) và cậu đến \(j\) tại thời điểm \(t+1\).
4. Nếu chọn kết thúc, hành trình thành công khi cậu đã đóng dấu ít nhất một lần; cậu nhận một món quà tại thị trấn kết thúc. Nếu chưa đóng dấu lần nào, hành trình thất bại.

Thời gian thực hiện mọi hành động ngoài việc đi giữa hai thị trấn là không đáng kể. JOI-kun không được đứng chờ tại một thị trấn.

Bạn là người tổ chức và phải chuẩn bị quà tại những thị trấn mà JOI-kun có thể kết thúc thành công. Do số quà có hạn, bạn muốn chuẩn bị quà ở ít thị trấn nhất có thể. Tuy nhiên, bạn chưa biết JOI-kun sẽ xuất phát từ đâu. Vì vậy, với mỗi thị trấn xuất phát \(s\) (\(1\le s\le N\)), hãy đếm số thị trấn \(g\) (\(1\le g\le N\)) sao cho tồn tại một hành trình thành công bắt đầu từ \(s\) và kết thúc tại \(g\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N\), \(D\).
• Dòng thứ hai chứa \(N\) số nguyên \(T_1, T_2, \ldots, T_N\).
• \(N-1\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(U_j\), \(V_j\) mô tả một con đường.

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(s\) chứa số thị trấn cần chuẩn bị quà nếu JOI-kun xuất phát từ thị trấn \(s\).

Ràng buộc

• \(2 \le N \le 400000\).
• \(0 \le D \le N-1\).
• \(0 \le T_i \le N\).
• \(1 \le U_j < V_j \le N\).
• Đồ thị các thị trấn là liên thông.
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (3 điểm): \(D \le 1\).
• Nhóm 2 (7 điểm): \(N \le 3000\) và \((U_j, V_j) = (j, j + 1)\) với mọi \(1 \le j \le N - 1\).
• Nhóm 3 (10 điểm): \(N \le 3000\).
• Nhóm 4 (11 điểm): \((U_j, V_j) = (j, j + 1)\) với mọi \(1 \le j \le N - 1\).
• Nhóm 5 (41 điểm): \(D = N - 1\), \(N \le 150000\).
• Nhóm 6 (28 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

2
3
4
2
2

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

2
1
2
0
1

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

2
2
7
5
1
2
5

Nguồn

JOI 2025/2026 Final Stage, Competition 3, problem Collecting Stamps 5. 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.