USACO 2023 - Tháng 1 - Hạng Bạch Kim - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2023 January Contest, Platinum, Tractor Paths	100 (p)	4.0s	512M
2	USACO 2023 January Contest, Platinum, Mana Collection	100 (p)	5.0s	512M
3	USACO 2023 January Contest, Platinum, Subtree Activation	100 (p)	2.0s	256M

1. USACO 2023 January Contest, Platinum, Tractor Paths

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Note: Giới hạn thời gian cho bài này là 4 giây và giới hạn bộ nhớ là 512MB.

Nông dân John có \(N\) \((2 \le N \le 2 \times 10^5)\) chiếc máy kéo, trong đó máy kéo thứ \(i\) chỉ có thể sử dụng trong khoảng thời gian \([l_i, r_i]\). Các khoảng thời gian của máy kéo có điểm đầu trái \(l_1 < l_2 < ... < l_n\) và điểm cuối phải \(r_1 \le r_2 \le ... \le r_n\). Một số máy kéo là đặc biệt.

Hai máy kéo \(i\) và \(j\) được gọi là kề nhau nếu \([l_i, r_i]\) và \([l_j, r_j]\) giao nhau. Nông dân John có thể chuyển từ một máy kéo sang bất kỳ máy kéo kề nhau nào. Một đường đi giữa hai máy kéo \(a\) và \(b\) bao gồm một chuỗi các lần chuyển, sao cho máy kéo đầu tiên trong chuỗi là \(a\), máy kéo cuối cùng là \(b\), và hai máy kéo liên tiếp trong chuỗi là kề nhau. Người ta đảm bảo rằng luôn có một đường đi giữa máy kéo \(1\) và máy kéo \(N\). Độ dài của một con đường là số lần chuyển (hoặc tương đương, số máy kéo trong đó trừ đi \(1\)).

Bạn được cho \(Q\) \((1 \le Q \le 2 \times 10^5)\) truy vấn, mỗi truy vấn chỉ định một cặp máy kéo \(a\) và \(b\) \((1 \le a < b \le N)\). Đối với mỗi truy vấn, hãy xuất ra hai số nguyên:

Độ dài của đường đi ngắn nhất giữa máy kéo \(a\) và máy kéo \(b\).
Số lượng máy kéo đặc biệt sao cho tồn tại ít nhất một đường đi ngắn nhất từ máy kéo \(a\) đến máy kéo \(b\) đi qua máy kéo đó.

Input

Dòng đầu tiên là số \(N\) và \(Q\)
Dòng thứ hai là xâu kí tự có độ dài \(2N\) chỉ bao gồm kí tự \('L'\) và \('R'\), biểu diễn cho thời điểm bắt đầu và kết thúc được xếp theo thứ tự. Với mọi tiền tố của xâu số lượng kí tự \('R'\) không vượt quá số lượng kí tự \('L'\), số lượng hai kí tự xuất hiện trong xâu bằng nhau. Vị trí của kí tự \('L'\) thứ \(i\) là biểu diễn cho thời gian máy thứ \(i\) có thể sử dụng, và vị trí của kí tự \('R'\) thứ \(i\) là biểu diễn cho thời gian máy thứ \(i\) không được sử dụng nữa.
Dòng tiếp theo là xâu nhị phân đồ dài \(N\) thể hiện các máy kéo đặc biệt, \(s_i = 1\) nếu máy kéo thứ \(i\) là đặc biệt, và ngược lại.
\(Q\) dòng tiếp theo gồm \(2\) số \(a\) và \(b\) thể hiện các truy vấn.

Output

Gồm \(Q\) dòng, mỗi dòng là \(2\) số là đáp án của các truy vấn in theo thứ tự trong đề bài.

Scoring

Subtask \(1\): \(N, Q \le 5000\).
Subtask \(2\): Có tối đa \(10\) máy kéo đặc biệt.
Subtask \(3\): Không có ràng buộc gì thêm

Test 1

Input

8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5

Output

Note

Có \(8\) máy kéo theo thứ tự như sau: \([1, 5], [2, 10], [3, 11], [4, 12], [6, 13], [7, 14], [8, 15], [9, 16]\).
Trong truy vấn thứ \(4\), có \(3\) đường đi ngắn nhất giữa máy kéo \(1\) và máy kéo \(5\). \(1 \rightarrow 2 \rightarrow 5\), \(1 \rightarrow 3 \rightarrow 5\), và \(1 \rightarrow 4 \rightarrow 5\). Độ dài của các đường đi này là \(2\).
Thêm nữa, mỗi máy kéo \(1, 2, 3, 4, 5\) là đều xuất hiện ít nhất một lần trong các đường đi trên, do vậy có tất cả \(4\) máy kéo đặc biệt xuất hiện là \(1, 2, 4, 5\).

2. USACO 2023 January Contest, Platinum, Mana Collection

Điểm: 100 (p) Thời gian: 5.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Note: Giới hạn thời gian là 5s. Giới hạn bộ nhớ là 512MB.

Bessie dạo này có một sự thích thú với ma thuật và cô bò đang thu thập mana cho một câu thần chú rất quan trọng. Bessie có \(N\) \((1 \le N \le 18)\) bể mana. Bể thứ \(i\) tích tụ được \(m_i\) mana mỗi giây \((1 \le m_i \le 10^8)\). Có \(M\) con đường giữa các bể mana này \((0 \le M \le N(N - 1))\), các đường đi này là một chiều, đường thứ \(i\) nối từ bể \(a_i\) sang bể \(b_i\), Bessie mất \(t_i\) giây để đi qua con đường này (\(1 \le a_i, b_i \le N\), \(a_i \ne b_i\), \(1 \le t_i \le 10^9\), mỗi cặp \((a_i, b_i)\) xuất hiện nhiều nhất một lần). Khi Bessie ở bể mana nào đó, cô nàng có thể lấy hết mana ở bể này và khiến nó trống không. Tại thời điểm \(0\), mọi bể mana đều trống không và cô nàng có thể bất kì bể nào để bắt đầu.

Hãy trả lời \(Q\) truy vấn \((1 \le Q \le 2 \times 10^5)\), mỗi truy vấn gồm \(2\) số nguyên là \(s\) và \(e\) \((1 \le s \le 10^9, 1 \le e \le N)\), bạn cần cho biết lượng mana lớn nhất cô nàng có thể thu thập được và ở giây thứ \(s\), cô nàng phải ở bể \(e\).

Input

Dòng đầu là số \(N\) và \(M\).
Dòng thứ hai là các số \(m_1, m_2, ..., m_N\).
Trong \(M\) dòng tiếp theo, dòng thứ \(i\) là bộ ba số \((a_i, b_i, t_i)\).
Dòng tiếp theo là số \(Q\).
\(Q\) dòng tiếp theo, mỗi dòng là hai số nguyên \(s\) và \(e\) thể hiện một truy vấn.

Output

\(Q\) dòng là đáp án của các truy vấn.

Scoring

Subtask \(1\): \(N \le 10, Q \le 100\).
Subtask \(2\): \(N \le 10\).
Subtask \(3\): \(Q \le 100\).
Subtask \(4\): \(N = 16\).
Subtask \(5\): \(N = 17\).
Subtask \(6\): Không có ràng buộc gì thêm.

Test 1

Input

Output

Note

Truy vấn đầu tiên: Bessie lấy \(5\) mana từ bể \(1\) sau \(5\) giây.
Truy vấn thứ hai: Bessie lấy \(50\) mana từ bể \(2\) sau \(5\) giây.
Truy vấn thứ ba: Bessie lấy \(100\) mana từ bể \(1\) sau \(100\) giây.
Truy vấn thứ tư: Bessie lấy \(90\) mana từ bể \(1\) sau \(90\) giây và \(1000\) mana từ bể \(2\) sau \(100\) giây.

Test 2

Input

4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4

Output

160000000
239999988050000000
119992550000000

3. USACO 2023 January Contest, Platinum, Subtree Activation

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Để chuẩn bị cho lễ Giao Thừa, Bessie cùng những người bạn của cô ấy đã dựng lên một cây thông với vô vàn bóng đèn lộng lẫy. Bessie có khả năng bật tắt các bóng đèn này thông qua một chiếc điều khiển. Trước lúc bình minh, cô nàng muốn thay đổi trạng thái của một số bóng đèn theo một số thứ tự (tất nhiên một bóng đèn có thể được thay đổi trạng thái vô số lần) sao cho lúc bắt đầu và kết thúc, tất cả các bóng đèn đều tắt. Bessie nghĩ rằng cây thông trông sẽ thật ngầu nếu như tập hợp các bóng đèn được bật tạo thành một cây con có gốc là một nút nào đó trong cây thông. Cô nàng muốn thứ tự thay đổi trạng thái của các bóng đèn thoả mãn điều kiện rằng, với mọi nút trong cây, tại một thời điểm nào đó, tập hợp các bóng đèn được bật sẽ tạo thành cây con có gốc là nút này. Thêm nữa, Bessie sẽ tốn năng lượng để bật/tắt các bóng đèn nên cô nàng muốn dùng năng lượng ít nhất có thể.

Nói cách khác, cho một cây \(N\) nút có gốc là \(1\) \((2 \le N \le 2 \times 10^5)\) đại diện cho \(N\) bóng đèn. Ban đầu tất cả bóng đèn đều tắt. Ở mỗi thao tác, cô nàng có thể chuyển trạng thái của một đỉnh từ tắt sang bật và ngược lại. In ra độ dài ngắn nhất của dãy các thao tác của cô nàng sao cho:

Mọi bóng đèn đều tắt sau dãy các thao tác.
Tập hợp các đỉnh trong cây con có gốc là đỉnh \(r\) là các đỉnh \(v\) sao cho \(r\) nằm trên đường đi từ \(1\) đến \(v\). Với mọi cây con của cây, tập hợp các đỉnh trong cây con này bằng với tập hợp các bóng đèn được bật sau khi thực hiện xong một số thao tác.

Input

Dòng đầu tiên là số \(N\).
Dòng tiếp theo là các số \(p_2, p_3, ..., p_N\) \((1 \le p_i < i,\) \(p_i\) là đỉnh cha của đỉnh \(i)\).

Output

Độ dài ngắn nhất của dãy thao tác.

Scoring

Subtask \(1\): \(N \le 8\).
Subtask \(2\): \(N \le 40\).
Subtask \(3\): \(N \le 5000\).
Subtask \(4\): Không có ràng buộc gì thêm.

Test 1

Input

3
1 1

Output

Note

Dãy thao tác sẽ được thực hiện như sau:

Đổi trạng thái của đỉnh 2.
(Các đỉnh được bật tạo thành cây con có gốc là 2).
Đổi trạng thái của đỉnh 1.
Đổi trạng thái của đỉnh 3.
(Các đỉnh được bật tạo thành cây con có gốc là 1).
Đổi trạng thái của đỉnh 1.
Đổi trạng thái của đỉnh 2.
(Các đỉnh được bật tạo thành cây con có gốc là 3).
Đổi trạng thái của đỉnh 3.
(Tất cả các đỉnh đều tắt).