LQDOJ Cup 2024 - Round #5 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	LQDOJ Cup 2024 - Round #5 - Đi thuyền	700 (p)	1.5s	1G
2	LQDOJ Cup 2024 - Round #5 - Lịch trình mê cung	700 (p)	1.0s	1G
3	LQDOJ Cup 2024 - Round #5 - Chia nhóm	600 (p)	1.5s	1G

1. LQDOJ Cup 2024 - Round #5 - Đi thuyền

Điểm: 700 (p) Thời gian: 1.5s Bộ nhớ: 1G Input: boat.inp Output: boat.out

Cho một thành phố trên biển gồm \(n\) ngôi nhà và \(m\) cây cầu \(2\) chiều. Bạn có thể chọn xuất phát tại nhà bất kì. Cho \(t\) ngày, mỗi ngày sẽ có một chuyến đi thuyền giữa hai nhà \(u\) và \(v\). Tại ngày thứ \(t\), bạn có thể chọn ở lại nhà hiện tại; hoặc nếu bạn đang ở nhà \(u\) thì có thể đi thuyền đến nhà \(v\); hoặc nếu bạn đang ở nhà có cầu nối trực tiếp với nhà \(u\) thì bạn có thể đến nhà \(u\) và đi thuyền sang nhà \(v\). Hãy tìm cách chọn điểm xuất phát và cách đi sao cho có thể đi thuyền nhiều nhất.

Input

Dòng đầu chứa ba số nguyên \(n, m\) và \(t\) \((1 \leq n, t \leq 5 \times 10^{5}, 1 \leq m \leq 10^{6})\) lần lượt là số ngôi nhà, số cây cầu và số ngày.
\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n, u \neq v)\) mô tả một cây cầu. Dữ liệu đảm bảo không có \(2\) cây cầu cùng nối nhà \(a\) và \(b\).
\(t\) dòng tiếp theo, mỗi dòng chứa hai số \(u\) và \(v\) \((1 \leq u, v \leq n, u \neq v)\) mô tả một chuyến đi thuyền.

Output

In ra một số nguyên duy nhất là số lần đi thuyền nhiều nhất có thể.

Scoring

Subtask \(1\) (\(22\%\) số điểm): \(t \leq 20, n \leq 1000\).
Subtask \(2\) (\(23\%\) số điểm): \(t,n \leq 10^{4}\).
Subtask \(3\) (\(27\%\) số điểm): \(t \leq 5000\).
Subtask \(4\) (\(28\%\) số điểm): Không có điều kiên gì thêm.

Example

Test 1

Input

Output

Note

Ở test thứ nhất, một trong các cách tối ưu là xuất phát tại điểm \(7\):

Ngày \(1\): Đi thuyền từ nhà \(7\) sang nhà \(6\).
Ngày \(2\): Đi cầu từ nhà \(6\) sang nhà \(1\). Đi thuyền từ nhà \(1\) sang nhà \(5\).
Ngày \(3\): Đi cầu từ nhà \(5\) sang nhà \(1\). Đi thuyền từ nhà \(1\) sang nhà \(2\).
Ngày \(4\): Không di chuyển.
Ngày \(5\): Đi cầu từ nhà \(2\) sang nhà \(3\), đi thuyền từ nhà \(3\) sang nhà \(2\).

Test 2

Input

Output

Note

Ở test thứ hai, một trong các cách tối ưu là xuất phát tại điểm \(2\):

Ngày \(1\): Đi thuyền từ nhà \(2\) sang nhà \(5\).
Ngày \(2\): Đi cầu từ nhà \(5\) sang nhà \(7\). Đi thuyền từ nhà \(7\) sang nhà \(6\).
Ngày \(3\): Không di chuyển.
Ngày \(4\): Không di chuyển.
Ngày \(5\): Không di chuyển.
Ngày \(6\): Đi thuyền từ nhà \(6\) sang nhà \(2\).
Ngày \(7\): Đi thuyền từ nhà \(2\) sang nhà \(3\).

2. LQDOJ Cup 2024 - Round #5 - Lịch trình mê cung

Điểm: 700 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: maze.inp Output: maze.out

GSFOS có dự định thám hiểm một mê cung, bằng cách thần kì nào đó mà anh ấy đã lấy được bản thiết kế của mê cung này. Mê cung gồm \(n\) phòng nối liên thông với nhau bằng \(n - 1\) con đường trực tiếp, con đường trực tiếp thứ \(i\) (\(1 \le i < n\)) nối hai phòng \(u_i\) và \(v_i\) với nhau, có độ dài là \(w_i\). Cửa ra/vào mê cung được đặt ở những phòng chỉ có một con đường nối đến trực tiếp.

Để thuận tiện cho việc thám hiểm mê cung, GSFOS cần chọn ra một đường đi trên mê cung nối hai đỉnh \(u\) đến \(v\) bất kì sao cho gọi tập đỉnh của đường đi này lần lượt là \(S= \{u,x_1,x_2,...,x_k,v\}\) thì ta luôn có cạnh trực tiếp nối từ \(u\) tới \(x_1\), \(x_1\) tới \(x_2\), \(\ldots\), \(x_k\) tới \(v\). Ta kí hiệu độ dài của đường đi từ \(u\) tới \(v\) là \(value(u,v)\). Tiếp theo, GSFOS cần chọn ra một đỉnh không thuộc tập đỉnh \(S\) đã chọn trước đó, coi đỉnh tìm được là đỉnh \(y\) thì ta kí hiệu độ dài của đường đi từ đỉnh \(y\) tới một trong các đỉnh thuộc tập đỉnh \(S\) sao cho giá trị này là nhỏ nhất có thể là \(distance(y,S)\). Giá trị của cách chọn này chính bằng \(value(u,v) \times distance(y,S)\).

Lưu ý, nếu không chọn được đỉnh \(y\) thoả mãn thì \(distance(y,S) = 0\), nếu không chọn được hai đỉnh \(u,v\) thoả mãn để làm đường đi thì \(value(u,v) = 0\).

GSFOS muốn tối đa hoá giá trị \(value(u,v) \times distance(y,S)\). Hãy giúp GSFOS tính giá trị lớn nhất của bài toán.

Input

Dòng thứ nhất chứa một số nguyên dương \(n\) \((1 \leq n \leq 3 \times 10^{5})\) là số lượng phòng trong mê cung.
\(n - 1\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(u, v\) và \(w\) \((1 \leq u, v \leq n, 1 \leq w \leq 10^{3})\) thể hiện có đường đi trực tiếp giữa phòng \(u\) và \(v\), độ dài của đường đó là \(w\).

Output

Gồm một số nguyên duy nhất là độ quan trọng lớn nhất.

Scoring

Subtask \(1\) (\(10\%\) số điểm): \(n \leq 100\).
Subtask \(2\) (\(20\%\) số điểm): \(n \leq 3000\).
Subtask \(3\) (\(30\%\) số điểm): Mỗi phòng của mê cung có tối đa \(3\) đường nối trực tiếp đến.
Subtask \(4\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input

Output

Note

Một trong những đường đi cho ra độ quan trọng lớn nhất là đường đi từ phòng \(2\) đến phòng \(5\), đường này có độ dài là \(5\), phòng có khoảng cách lớn nhất với đường đi này là phòng \(4\), có khoảng cách với đường quan trọng kia là \(3\), lúc này độ quan trọng của đường đi sẽ là \(5 \times 3 = 15\)

3. LQDOJ Cup 2024 - Round #5 - Chia nhóm

Điểm: 600 (p) Thời gian: 1.5s Bộ nhớ: 1G Input: divgroup.inp Output: divgroup.out

Thiết Mộc Chân có một đội quân vô cùng hùng mạnh, ông quyết dùng đội quân này để đi xâm lược mở rộng lãnh thổ. Đội quân của ông có \(n\) chiến binh được đánh số từ \(1\) đến \(n\) có sức mạnh lần lượt là \(a_{1}, a_{2}, \ldots, a_{n}\).

Mỗi chiến binh trong đội quân của ông đều có niềm kiêu hãnh vô cùng lớn nên nếu được phân nhóm,chiến binh đó không muốn có ai khác trong nhóm có cùng sức mạnh với mình.

Giả sử Thiết Mộc Chân chọn một nhóm \(k\) người có sức mạnh là \((x_{1}, x_{2}, \ldots, x_{k})\) thì nhóm này sẽ được chia ra như sau:

Nếu nhóm này không có \(2\) chiến binh nào có sức mạnh bằng nhau thì dừng lại.
Nếu nhóm này có ít nhất \(2\) chiến có sức mạnh bằng nhau thì ta chia nhóm này thành \(2\) nhóm các chiến binh chỉ số lẻ \((x_{1}, x_{3}, \ldots)\), và nhóm các chiến binh có chỉ số chẵn \((x_{2}, x_{4}, \ldots)\) và sau đó ta lại tiếp tục quy trình chia như đã nói với \(2\) nhóm này.

Và với một nhóm như vậy Thiết Mộc Chân cần biết nhóm đó được tách thành bao nhiêu nhóm qua quy trình trên để ông bàn chiến thuật tác chiến.

Thiết Mộc Chân muốn thử nghiệm \(q\) giả định chiến đấu, cụ thể như sau:

Với gỉa định chiến đấu thứ \(i\) ông sẽ chọn ra một nhóm gồm các binh sĩ có chỉ số sức mạnh \((a_{l_i}, a_{l_i+1}, \ldots,a_{r_i})\) để đi chiến đấu. Với mỗi ngày, bạn hãy giúp Thiết Mộc Chân tính xem số nhóm được chia ra từ nhóm ông đã chọn nhé.

Input

Dòng đầu gồm hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{5})\) lần lượt là số binh lính và số ngày đánh trận.
Dòng thứ \(2\) gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq n)\) là sức mạnh của các binh lính.
\(q\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(l\) và \(r\) \((1 \leq l \leq r \leq n)\) mô tả nhóm Thiết Mộc Chân chọn đi chiến đấu vào ngày thứ \(i\).

Output

Gồm \(q\) dòng, dòng thứ \(i\) là một số nguyên là số nhóm chia ra được vào ngày thứ \(i\).

Scoring

Subtask \(1\) (\(7\%\) số điểm): \(a_{i} = 1\) với mọi \(i\) từ \(1\) đến \(n\);
Subtask \(2\) (\(13\%\) số điểm): \(n, q \leq 10^{3}\).
Subtask \(3\) (\(15\%\) số điểm): \(n \leq 10^{3}\) và \(l_{i} = 1, \forall i:1 \leq i \leq q\)
Subtask \(4\) (\(17\%\) số điểm): \(n \leq 10^{3}\).
Subtask \(5\) (\(23\%\) số điểm): \(n, q \leq 10^{4}\).
Subtask \(6\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input

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

Output

1
2
3

Note

Ở truy vấn thứ nhất nhóm được chọn gồm \(\{1, 2, 4, 3\}\) không có \(2\) người nào có sức mạnh trùng nhau nên ta không chia thêm nên kết quả truy vấn này là \(1\) nhóm.
Ở truy vấn thứ hai nhóm được chọn gồm \(\{2, 4, 3, 2\}\) có \(2\) người cùng sức mạnh là \(2\) nên nhóm được chia tiếp thành \(2\) nhóm là \(\{2, 3\}\) và \(\{4, 2\}\),đến đây không nhóm nào có \(2\) người trùng sức mạnh với nhau nên ta không chia thêm được nữa và kết quả ở truy vấn này là \(2\) nhóm.

Test 2

Input

Output

5
3