USACO 2011 - Tháng 12 - Hạng Vàng

Hôm nay những chú bò đặc biệt tinh nghịch! Nông dân John chỉ muốn chụp một bức ảnh những chú bò đang đứng thành hàng, nhưng chúng cứ di chuyển ngay trước khi ông kịp bấm máy.

Cụ thể, mỗi chú trong số \(N\) (\(1 \le N \le 20\,000\)) chú bò của FJ có một số hiệu nguyên duy nhất. FJ muốn chụp những chú bò đứng thành hàng theo một thứ tự rất cụ thể, được biểu diễn bởi nội dung của mảng \(A[1..N]\), trong đó \(A[j]\) là số hiệu của chú bò thứ \(j\) trong thứ tự này. Ông xếp những chú bò theo đúng thứ tự đó, nhưng ngay trước khi ông kịp nhấn nút chụp ảnh, một nhóm gồm không hoặc nhiều chú bò (không nhất thiết liên tiếp) chuyển đến một tập hợp vị trí mới trong hàng. Chính xác hơn, một nhóm gồm không hoặc nhiều chú bò bước ra khỏi hàng, còn những chú bò ở lại dịch chuyển để lấp các khoảng trống vừa tạo ra. Sau đó, những chú bò đã bước ra chen trở lại vào các vị trí khác trong hàng (không nhất thiết là vị trí ban đầu của chúng). Dù bực mình nhưng không nản chí, FJ lại xếp đàn bò theo thứ tự trong \(A\); tuy nhiên, ngay trước lúc ông kịp chụp, một nhóm khác gồm không hoặc nhiều chú bò lại chuyển đến một tập hợp vị trí mới trong hàng.

Quá trình trên lặp lại cho đến khi FJ chụp tổng cộng năm bức ảnh rồi bỏ cuộc. Cho biết nội dung của từng bức ảnh, hãy khôi phục thứ tự dự định ban đầu \(A\). Mỗi bức ảnh cho thấy một thứ tự của đàn bò khác với \(A\) ở chỗ một nhóm gồm không hoặc nhiều chú bò đã di chuyển. Tuy nhiên, mỗi chú bò chỉ di chuyển trong nhiều nhất một bức ảnh: nếu một chú bò thuộc nhóm di chuyển trong một bức ảnh thì nó sẽ không chủ động di chuyển trong bất kỳ bức ảnh nào trong bốn bức còn lại (tất nhiên, chỉ số vị trí của nó vẫn có thể thay đổi do những chú bò xung quanh di chuyển).

Dữ liệu vào

• Dòng đầu tiên chứa số lượng bò \(N\) (\(1 \le N \le 20\,000\)).
• \(5N\) dòng tiếp theo mô tả năm thứ tự, mỗi thứ tự là một khối gồm \(N\) dòng liên tiếp. Mỗi dòng chứa số hiệu của một chú bò, là một số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Dữ liệu ra

• Gồm \(N\) dòng mô tả thứ tự dự định \(A\), mỗi dòng chứa một số hiệu.

Ví dụ

5
10
20
30
40
50
20
10
30
40
50
30
10
20
40
50
40
10
20
30
50
50
10
20
30
40

10
20
30
40
50

Nguồn

USACO 2011 December Contest, Silver Division — Cow Photography

Tác giả đề: Brian Dean, 2011.

Nông dân John đang theo học một lớp thuật toán buổi tối tại trường đại học địa phương, và ông vừa học về cây khung nhỏ nhất. Tuy nhiên, giờ đây Nông dân John nhận ra rằng thiết kế trang trại của mình chưa hiệu quả như mong muốn và ông muốn đơn giản hóa bố cục trang trại.

Trang trại hiện được bố trí như một đồ thị, trong đó các đỉnh biểu diễn những cánh đồng và các cạnh biểu diễn những con đường giữa các cánh đồng, mỗi con đường có một độ dài tương ứng. Nông dân John nhận thấy rằng với mỗi giá trị độ dài, nhiều nhất ba con đường trong trang trại có cùng độ dài đó. FJ muốn loại bỏ một số con đường để trang trại trở thành một cây — tức là giữa mọi cặp cánh đồng chỉ có duy nhất một lộ trình. Hơn nữa, Nông dân John muốn cây này là một cây khung nhỏ nhất — một cây có tổng độ dài các cạnh nhỏ nhất có thể.

Hãy giúp Nông dân John tính không chỉ tổng độ dài các cạnh của một cây khung nhỏ nhất được tạo từ đồ thị trang trại, mà còn cả số cây khung nhỏ nhất khác nhau mà ông có thể tạo ra.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 40\,000\); \(1 \le M \le 100\,000\)), lần lượt biểu diễn số đỉnh và số cạnh trong đồ thị trang trại. Các đỉnh được đánh số từ \(1\) đến \(N\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i\), \(b_i\) và \(n_i\) (\(1 \le a_i,b_i \le N\); \(1 \le n_i \le 1\,000\,000\)), biểu diễn một cạnh nối đỉnh \(a_i\) với đỉnh \(b_i\) có độ dài \(n_i\). Không có độ dài cạnh \(n_i\) nào xuất hiện quá ba lần.

Dữ liệu ra

• Dòng đầu tiên chứa hai số nguyên biểu diễn độ dài của cây khung nhỏ nhất và số lượng cây khung nhỏ nhất (lấy modulo \(1\,000\,000\,007\)).

Ví dụ

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

4 3

Nguồn

USACO 2011 December Contest, Gold Division — Simplifying the Farm

Tác giả đề: Nathan Pinsker, 2011.

Nông dân John có \(N\) đồng cỏ cằn cỗi (\(2 \le N \le 100\,000\)) được nối với nhau bởi \(N-1\) con đường hai chiều, sao cho giữa hai đồng cỏ bất kỳ có đúng một đường đi. Bessie, một chú bò rất yêu thích thời gian gặm cỏ, thường phàn nàn rằng trên những con đường giữa các đồng cỏ không có cỏ. Nông dân John rất yêu quý Bessie, và hôm nay cuối cùng ông cũng sẽ trồng cỏ trên các con đường. Ông sẽ thực hiện việc này bằng một quy trình gồm \(M\) bước (\(1 \le M \le 100\,000\)).

Ở mỗi bước, một trong hai việc sau sẽ xảy ra:

• FJ chọn hai đồng cỏ và trồng một mảng cỏ dọc theo mỗi con đường nằm trên đường đi giữa hai đồng cỏ đó; hoặc
• Bessie hỏi có bao nhiêu mảng cỏ trên một con đường cụ thể, và Nông dân John phải trả lời câu hỏi của cô.

Nông dân John đếm rất kém — hãy giúp ông trả lời các câu hỏi của Bessie!

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách, mô tả hai đầu mút của một con đường.
• \(M\) dòng tiếp theo; dòng thứ \(i\) mô tả bước thứ \(i\). Ký tự đầu tiên của dòng là P hoặc Q, cho biết FJ đang trồng cỏ hay chỉ thực hiện truy vấn. Theo sau là hai số nguyên \(A_i\) và \(B_i\) (\(1 \le A_i,B_i \le N\)) cách nhau bởi dấu cách, mô tả hành động hoặc truy vấn của FJ.

Dữ liệu ra

• Mỗi dòng chứa câu trả lời cho một truy vấn, theo đúng thứ tự các truy vấn xuất hiện trong dữ liệu vào.

Ví dụ

4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4

2
1
2

Nguồn

USACO 2011 December Contest, Gold Division — Grass Planting

Tác giả đề: Travis Hance, 2011.