USACO 2022 - Tháng 12 - Hạng Bạch Kim

Trang trại của Farmer John có thể được mô phỏng như một đồ thị có hướng với trọng số, với các con đường (cạnh) kết nối các nút khác nhau, và trọng số của mỗi cạnh là thời gian cần thiết để di chuyển trên con đường đó. Mỗi ngày, Bessie thích di chuyển từ chuồng (nằm ở nút \(1\)) đến cánh đồng (nằm ở nút \(N\)) bằng cách đi qua chính xác \(K\) con đường, và muốn đến cánh đồng nhanh nhất có thể dưới ràng buộc này. Tuy nhiên, tại một thời điểm nào đó, các con đường sẽ ngừng được bảo trì, và một cách tuần tự, chúng bắt đầu hỏng, trở nên không thể đi qua. Hãy giúp Bessie tìm đường đi ngắn nhất từ chuồng đến cánh đồng vào mọi thời điểm!

Cụ thể, chúng ta bắt đầu với một đồ thị \(N\) đỉnh (\(1\le N\le 300\)) có hướng hoàn chỉnh có trọng số với \(N^2\) cạnh: một cạnh cho mỗi cặp \((i, j)\) với \(1 \le i, j \le N\) (lưu ý rằng có \(N\) vòng lặp tự thân). Sau mỗi lần loại bỏ, hãy xuất ra trọng số tối thiểu của bất kỳ đường đi nào từ \(1\) đến \(N\) đi qua chính xác \(K\) (\(2\le K\le 8\)) cạnh (không nhất thiết phải khác nhau). Lưu ý rằng sau lần loại bỏ thứ \(i\), đồ thị còn lại \(N^2-i\) cạnh.

Trọng số của một đường đi được định nghĩa là tổng trọng số của tất cả các cạnh trên đường đi. Lưu ý rằng một đường đi có thể chứa nhiều cạnh giống nhau và nhiều đỉnh giống nhau, bao gồm cả các đỉnh \(1\) và \(N\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).
• \(N\) dòng tiếp theo, mỗi dòng có \(N\) số nguyên. Số nguyên thứ \(j\) của dòng \(i\) là \(w_{ij}\) (\(1\le w_{ij}\le 10^8\)).
• Sau đó là \(N^2\) dòng, mỗi dòng chứa hai số nguyên \(i\) và \(j\) (\(1\le i,j\le N\)). Mỗi cặp số nguyên xuất hiện chính xác một lần.

Output

• Chính xác \(N^2\) dòng, trọng số tối thiểu của đường đi \(K\) sau mỗi lần loại bỏ. Nếu không còn đường đi \(K\) nào tồn tại thì xuất ra \(-1\).

Scoring

• Subtask 1: \(K=\lfloor (T+3)/2\rfloor\).
• Subtask 2: Không có ràng buộc gì thêm.

Example

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

11
18
22
22
22
-1
-1
-1
-1

Có \(M\) (\(1\le M\le 2\cdot 10^5\)) cặp bạn bè ban đầu giữa \(N\) (\(2\le N\le 2\cdot 10^5\)) con bò được gán nhãn từ \(1\) đến \(N\). Các con bò sẽ rời trang trại để đi nghỉ một cách lần lượt. Vào ngày thứ \(i\), con bò thứ \(i\) rời trang trại, và tất cả các cặp bạn bè của con bò thứ \(i\) vẫn có mặt tại trang trại sẽ trở thành bạn bè. Hãy cho biết tổng số tình bạn mới được hình thành là bao nhiêu.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• Các dòng tiếp theo chứa \(M\) dòng, mỗi dòng có hai số nguyên \(u_i\) và \(v_i\) cho biết rằng bò \(u_i\) và bò \(v_i\) là bạn bè (\(1\le u_i,v_i\le N\), \(u_i\neq v_i\)). Không có cặp bò nào xuất hiện nhiều hơn một lần.

Output

• Một dòng chứa tổng số tình bạn mới được hình thành. Không bao gồm các cặp bò đã là bạn bè từ trước.

Scoring

• Subtask 1: \(N\le 500\).
• Subtask 2: \(N\le 10^4\).
• Subtask 3: Không có ràng buộc gì thêm.

Example

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

5

Liên Hiệp Bò của Farmer John (UCFJ) đang tham gia giải vô địch hoofball hàng năm! Đội UCFJ gồm \(N\) bò (\(1 \le N \le 7500\)) đã giành được huy chương vàng trong môn hoofball, vượt qua đội của Farmer Nhoj một cách sát sao.

Các con bò đã sắp xếp hàng để chuẩn bị cho buổi lễ trao giải. Chúng muốn John chụp \(\frac{N(N+1)}{2}\) bức ảnh nhóm, một bức cho mỗi chuỗi con liên tiếp trong đội hình.

Tuy nhiên, John, với tư cách là huấn luyện viên của đội, rất kén chọn về cách mà các con bò nên được xếp hàng. Cụ thể, ông từ chối chụp ảnh cho một chuỗi con trừ khi nó tạo thành một palindrome, có nghĩa là giống bò của con bò thứ \(i\) từ đầu chuỗi con phải giống với giống bò của con bò thứ \(i\) từ cuối chuỗi con đối với tất cả các số nguyên dương \(i\) nhỏ hơn hoặc bằng độ dài của chuỗi con. Mỗi giống bò có thể là Guernsey hoặc Holstein.

Đối với mỗi một trong \(\frac{N(N+1)}{2}\) chuỗi con liên tiếp của đội hình, hãy đếm số lần hoán đổi tối thiểu cần thiết để sắp xếp chuỗi con đó thành một palindrome (hoặc \(-1\) nếu không thể làm được). Một lần hoán đổi đơn giản là việc lấy hai con bò kề nhau trong chuỗi con và hoán đổi vị trí của chúng. Xuất ra tổng số lần hoán đổi của tất cả các chuỗi con này.

Lưu ý rằng số lần hoán đổi cần thiết được tính độc lập cho mỗi chuỗi con (các con bò quay trở lại vị trí ban đầu giữa các bức ảnh).

Input

• Đội hình, được biểu diễn bằng một chuỗi gồm các ký tự G và H có độ dài \(N\).

Output

• Tổng số lần hoán đổi được đề cập trên đối với tất cả \(\frac{N(N+1)}{2}\) chuỗi con liên tiếp của đội hình.

Scoring

• Subtask 1: \(N \in [100, 200, 500, 1000, 2000, 5000, 5000, 5000, 5000, 5000, 7500, 7500, 7500, 7500, 7500]\).

Example

GHHGGHHGH

12