JOI 2015 Open Contest

Đây là một bài chỉ xuất kết quả (output-only).

Năm 2018, Kỳ thi Olympic Tin học Quốc tế sẽ được tổ chức tại Nhật Bản. Để chào mừng sự kiện này, ban tổ chức IOI dự định tạo một tác phẩm nghệ thuật có "thiết kế hơi kỳ lạ" và trang trí nó tại địa điểm thi. Ban tổ chức đã nhờ Công ty TNHH JOI (Just Odd Inventions) thiết kế tác phẩm. Các nhà thiết kế của JOI đề xuất như sau:

• Tác phẩm được tạo trên một bảng hình chữ nhật gồm \(H \times W\) ô. Ta sẽ lát bảng bằng \(N\) viên gạch và các viên gạch không chồng lên nhau.
• Viên gạch thứ \(i\) (\(1 \le i \le N\)) có kích thước \(1 \times 1\) hoặc \(1 \times 2\), và có màu \(C_i\).
• Có thể xoay một viên gạch kích thước \(1 \times 2\) để dùng nó như một viên gạch kích thước \(2 \times 1\).

Họ cũng đã đề xuất các loại gạch dùng cho tác phẩm, nhưng lại chưa đề xuất cách lát gạch trên bảng, vốn là phần quan trọng nhất của thiết kế. Vì các thiết kế của JOI luôn đẹp, ban tổ chức quyết định giữ nguyên các loại gạch do JOI đề xuất và tự tìm cách lát sao cho độ đẹp của tác phẩm lớn nhất.

Độ đẹp được tính như sau:

• Với mỗi cạnh chung của hai ô thuộc hai viên gạch có màu lần lượt là \(j\) và \(k\), cạnh đó đóng góp \(A_{j,k}\) điểm.
• Độ đẹp của tác phẩm là tổng điểm của tất cả các cạnh như vậy.

Nếu hai viên gạch kích thước \(1 \times 2\) tiếp xúc nhau qua cạnh của hai cặp ô, điểm của cả hai cạnh đều được tính riêng.

Hãy xác định một cách lát các viên gạch lên bảng sao cho độ đẹp lớn nhất có thể.

Dữ liệu vào

Bài có năm nhóm. Mỗi nhóm tương ứng với một tệp dữ liệu vào công khai. Bạn cần tải đủ năm tệp 01.txt, 02.txt, 03.txt, 04.txt, 05.txt trong phần tệp đính kèm của đề bài và tạo một tệp kết quả tương ứng cho mỗi tệp dữ liệu vào.

Mỗi tệp dữ liệu vào có định dạng sau:

• Dòng đầu chứa bốn số nguyên \(H\), \(W\), \(K\), \(N\), lần lượt cho biết bảng có \(H \times W\) ô, có \(K\) màu gạch và có \(N\) viên gạch.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N\)) chứa hai số nguyên \(S_i\), \(C_i\). Viên gạch thứ \(i\) có kích thước \(1 \times S_i\) và màu \(C_i\).
• Trong \(K\) dòng tiếp theo, dòng thứ \(j\) (\(1 \le j \le K\)) chứa \(K\) số nguyên \(A_{j,1}, A_{j,2}, \ldots, A_{j,K}\). Khi hai viên gạch màu \(j\) và \(k\) có chung một cạnh, cạnh đó đóng góp \(A_{j,k}\) điểm.

Dữ liệu ra

Với mỗi tệp dữ liệu vào, hãy nộp một tệp kết quả gồm đúng \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) mô tả vị trí của viên gạch thứ \(i\):

• Nếu \(S_i = 1\), dòng thứ \(i\) chứa hai số nguyên \(R_i\), \(C_i'\). Viên gạch thứ \(i\) được đặt tại ô ở hàng \(R_i\) tính từ trên xuống và cột \(C_i'\) tính từ trái sang.
• Nếu \(S_i = 2\), dòng thứ \(i\) chứa bốn số nguyên \(R_i\), \(C_i'\), \(R_i'\), \(C_i''\). Viên gạch thứ \(i\) phủ hai ô \((R_i, C_i')\) và \((R_i', C_i'')\).

Một tệp kết quả hợp lệ phải thỏa mãn tất cả các điều kiện sau:

• Mọi tọa độ đều nằm trên bảng.
• Với viên gạch kích thước \(1 \times 2\), hai ô được chỉ ra phải khác nhau và có chung một cạnh.
• Không có hai viên gạch nào phủ cùng một ô.
• Mọi ô của bảng đều được phủ bởi đúng một viên gạch.
• Dòng thứ \(i\) phải mô tả đúng viên gạch thứ \(i\) và có đúng số lượng số nguyên theo kích thước của viên gạch đó.

Nếu tệp kết quả không hợp lệ, nhóm tương ứng nhận \(0\) điểm.

Ràng buộc

Mọi tệp dữ liệu vào thỏa mãn:

• \(1 \le H \le 100\).
• \(1 \le W \le 100\).
• \(1 \le K \le 100\).
• \(1 \le N \le 10\,000\).
• \(1 \le S_i \le 2\) (\(1 \le i \le N\)).
• \(1 \le C_i \le K\) (\(1 \le i \le N\)).

• \(0 \le A_{j,k} \le 1\,000\) (\(1 \le j,k \le K\)).
• \(A_{j,k} = A_{k,j}\) (\(1 \le j,k \le K\)).

Phân nhóm

Với ý nghĩa của \(X\) và \(Y\), xem phần Chấm điểm.

Chấm điểm

Mỗi nhóm gồm đúng một tệp dữ liệu vào và có tối đa \(20\) điểm. Gọi \(B\) là độ đẹp của cách lát trong tệp kết quả tương ứng.

• Nếu cách lát không hợp lệ, điểm của nhóm là \(0\).
• Nếu cách lát hợp lệ và \(B < X\), điểm của nhóm là \(0\).
• Nếu cách lát hợp lệ và \(X \le B < Y\), điểm của nhóm là

Tương đương, vì điểm là số nguyên, giá trị trên bằng

• Nếu cách lát hợp lệ và \(B \ge Y\), điểm của nhóm là \(20\).

Tổng điểm của bài là tổng điểm của năm nhóm, tối đa \(100\) điểm.

Ví dụ

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

2 2
1 1 1 2
3 2
3 1 2 1

Cộng hòa JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\). Các thành phố được nối bởi \(N-1\) con đường hai chiều. Người dân có thể đi giữa hai thành phố bất kỳ qua một hoặc nhiều con đường.

Ông IOI là ứng cử viên tổng thống Cộng hòa JOI. Để trở thành tổng thống, ông phải tiến hành chiến dịch tranh cử. Thư ký của ông đã lập \(M\) kế hoạch. Trong kế hoạch thứ \(i\), ông IOI đi từ thành phố \(A_i\) đến thành phố \(B_i\) qua số con đường ít nhất và diễn thuyết công khai tại mọi thành phố trên đường đi, bao gồm cả \(A_i\) và \(B_i\). Nếu thực hiện kế hoạch thứ \(i\), ông IOI sẽ nhận được \(C_i\) phiếu bầu. Ông có thể thực hiện nhiều kế hoạch.

Tuy nhiên, người dân Cộng hòa JOI rất thiếu kiên nhẫn. Nếu ông IOI diễn thuyết công khai nhiều hơn một lần tại cùng một thành phố, ông sẽ mất sự ủng hộ của họ.

Ông IOI muốn nhận được nhiều phiếu bầu nhất có thể, với điều kiện không diễn thuyết quá một lần tại bất kỳ thành phố nào. Hãy tính số phiếu bầu lớn nhất ông có thể nhận được.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa số nguyên \(N\), số thành phố của Cộng hòa JOI.
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N-1\)) chứa hai số nguyên \(X_i\), \(Y_i\). Con đường thứ \(i\) nối thành phố \(X_i\) và thành phố \(Y_i\).
• Dòng tiếp theo chứa số nguyên \(M\), số kế hoạch tranh cử.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le M\)) chứa ba số nguyên \(A_i\), \(B_i\), \(C_i\). Trong kế hoạch thứ \(i\), ông IOI đi từ \(A_i\) đến \(B_i\) theo đường có ít cạnh nhất và nhận được \(C_i\) phiếu bầu nếu thực hiện kế hoạch này.

Dữ liệu ra

In ra một số nguyên duy nhất: số phiếu bầu lớn nhất ông IOI có thể nhận được.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le X_i, Y_i \le N\) (\(1 \le i \le N-1\)).
• \(X_i \ne Y_i\) (\(1 \le i \le N-1\)).
• Có thể đi giữa hai thành phố bất kỳ qua một hoặc nhiều con đường.
• \(1 \le M \le 100\,000\).
• \(1 \le A_i, B_i \le N\) (\(1 \le i \le M\)).
• \(A_i \ne B_i\) (\(1 \le i \le M\)).
• \(1 \le C_i \le 10\,000\) (\(1 \le i \le M\)).

Phân nhóm

• Nhóm 1 (10 điểm)

• \(M \le 15\).

• Nhóm 2 (5 điểm)

• \(X_i = i\) và \(Y_i = i+1\) (\(1 \le i \le N-1\)).

• \(C_i = 1\) (\(1 \le i \le M\)).

• Nhóm 3 (5 điểm)

• \(X_i = i\) và \(Y_i = i+1\) (\(1 \le i \le N-1\)).

• Nhóm 4 (30 điểm)

• \(C_i = 1\) (\(1 \le i \le M\)).

• Nhóm 5 (10 điểm)

• \(N \le 1\,000\).

• \(M \le 1\,000\).

• Nhóm 6 (40 điểm)

Không có ràng buộc bổ sung.

Ví dụ

7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8

19

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
5
7 5 4
5 8 9
4 3 9
1 3 3
2 8 11

18

10
10 6
2 7
1 9
9 8
3 8
6 4
7 8
5 4
4 8
7
1 3 1
4 10 1
2 8 1
5 3 1
3 7 1
8 5 1
1 9 1

3

20
17 10
11 4
8 3
3 16
1 14
15 18
5 4
6 18
10 18
19 4
16 7
2 13
4 12
12 20
9 20
18 13
20 14
14 7
13 7
15
19 9 2341
13 8 6974
8 3 3339
15 17 6515
10 13 4370
1 7 8376
18 2 9272
6 7 4595
1 20 505
10 9 308
6 19 8937
2 15 5072
5 4 4217
2 4 4170
19 12 8204

29191

Ông JOI làm việc tại Công ty Dược phẩm IOI. Tại đây, các nhà nghiên cứu đang bận rộn thử nghiệm để phát triển những loại thuốc xịt khử khuẩn mới.

Độ mạnh của một loại thuốc xịt khử khuẩn được định nghĩa như sau: nếu dùng một lần thuốc xịt có độ mạnh \(x\) lên một đĩa nuôi cấy có \(y\) vi khuẩn, số vi khuẩn còn lại sẽ là \(\left\lfloor y/x \right\rfloor\).

Một loại thuốc xịt mới có độ mạnh \(K\) vừa được phát triển. Để kiểm tra hiệu quả của nó, các nhà nghiên cứu tiến hành thí nghiệm trên \(N\) đĩa nuôi cấy, được đánh số từ \(1\) đến \(N\). Ban đầu, đĩa thứ \(i\) có \(C_i\) vi khuẩn. Trong thí nghiệm, họ lần lượt thực hiện \(Q\) thao tác. Mỗi thao tác thuộc một trong ba loại sau:

• Thao tác 1: Chọn một đĩa \(a\) và một số nguyên \(b\), rồi điều chỉnh số vi khuẩn trên đĩa \(a\) thành \(b\).
• Thao tác 2: Chọn hai số nguyên \(l\), \(r\) với \(1 \le l \le r \le N\), rồi xịt thuốc đúng một lần lên từng đĩa \(l, l+1, \ldots, r\).
• Thao tác 3: Chọn hai số nguyên \(l\), \(r\) với \(1 \le l \le r \le N\), tính tổng số vi khuẩn trên các đĩa \(l, l+1, \ldots, r\) và ghi lại kết quả.

Giả sử thuốc xịt mới hoạt động đúng như dự kiến. Hãy xác định tất cả các số được ghi lại bởi các thao tác loại 3.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa ba số nguyên \(N\), \(Q\), \(K\), lần lượt là số đĩa nuôi cấy, số thao tác và độ mạnh của thuốc xịt.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N\)) chứa số nguyên \(C_i\), số vi khuẩn ban đầu trên đĩa thứ \(i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le Q\)) chứa ba số nguyên \(S_i\), \(T_i\), \(U_i\), mô tả thao tác thứ \(i\):
• Nếu \(S_i = 1\), đây là thao tác 1 với \(a = T_i\), \(b = U_i\).
• Nếu \(S_i = 2\), đây là thao tác 2 với \(l = T_i\), \(r = U_i\).
• Nếu \(S_i = 3\), đây là thao tác 3 với \(l = T_i\), \(r = U_i\).

Dữ liệu ra

Với mỗi thao tác loại 3, in số được ghi lại trên một dòng, theo đúng thứ tự thực hiện các thao tác. Số dòng kết quả bằng số thao tác loại 3.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le Q \le 100\,000\).
• \(1 \le K \le 10\).
• \(0 \le C_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).
• \(1 \le S_i \le 3\) (\(1 \le i \le Q\)).
• Nếu \(S_i = 1\), thì \(1 \le T_i \le N\) và \(0 \le U_i \le 1\,000\,000\,000\).
• Nếu \(S_i = 2\) hoặc \(S_i = 3\), thì \(1 \le T_i \le U_i \le N\).

Phân nhóm

• Nhóm 1 (5 điểm)

• \(N \le 3\,000\).

• \(Q \le 3\,000\).

• Nhóm 2 (10 điểm)

• \(C_i \le 1\) (\(1 \le i \le N\)).

• Với mọi thao tác có \(S_i = 1\), ta có \(U_i \le 1\).

• Nhóm 3 (10 điểm)

• \(K = 1\).

• Nhóm 4 (75 điểm)

Không có ràng buộc bổ sung.

Ví dụ

5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

8
3
8

15 10 3
25
87
32
89
24
99
57
88
10
57
65
42
66
98
13
3 9 12
1 7 15
3 2 9
2 1 14
3 10 13
1 10 6
2 14 14
1 7 96
3 14 15
3 10 12

174
444
76
23
41