BOI 2017 - Ngày 1

Một đảng chính trị có \(N\) thành viên muốn xây dựng những chính sách hoàn toàn mới. Để làm điều đó, đảng dự định thành lập một ủy ban phát triển chính sách mới. Rõ ràng, những chính sách tốt nhất được xây dựng khi mọi cặp thành viên trong ủy ban đều bất đồng với nhau, và khi ủy ban có càng nhiều thành viên càng tốt.

Để xác định những cặp chính trị gia nào bất đồng và những cặp nào không, đảng đã bố trí cho mọi cặp chính trị gia thảo luận về một chủ đề được chọn ngẫu nhiên. Mỗi khi hai chính trị gia không thể thống nhất về chủ đề được giao, điều đó được ghi lại trong Sổ Những Thành Tựu Vĩ Đại của đảng.

Với cuốn sổ này, bạn được giao nhiệm vụ tìm ủy ban lớn nhất mà mọi cặp thành viên đều bất đồng với nhau. Tuy nhiên, việc tìm một ủy ban lớn có thể không dễ dàng: qua phân tích kỹ lưỡng, người ta nhận thấy rằng với mọi nhóm không rỗng gồm các thành viên của đảng, luôn tồn tại ít nhất một người trong nhóm bất đồng với ít hơn \(K\) người khác trong chính nhóm đó. Vì vậy, ủy ban không thể có nhiều hơn \(K\) thành viên. Nhưng liệu có thể chọn được một ủy ban có đúng số thành viên này hay không? Hãy tìm số thành viên lớn nhất của một ủy ban mà không có hai người nào đồng ý với nhau.

Ảnh: Federal Open Market Committee, Federal Reserve Bank of Philadelphia, qua Wikimedia Commons; CC0, thuộc phạm vi công cộng.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\): số thành viên trong đảng và giá trị \(K\) được mô tả ở trên. Các thành viên được đánh số từ \(0\) đến \(N-1\).

Tiếp theo là \(N\) dòng, lần lượt ứng với các chính trị gia \(i=0,1,\ldots,N-1\). Dòng của chính trị gia \(i\) bắt đầu bằng số nguyên \(D_i\), theo sau là \(D_i\) số nguyên chỉ những thành viên khác mà người này bất đồng, theo Sổ Những Thành Tựu Vĩ Đại.

Dữ liệu ra

In ra một số nguyên: số thành viên lớn nhất có thể có trong ủy ban.

Ràng buộc

• \(0 \le D_i < N \le 50\,000\) với mọi \(0 \le i < N\).
• \(1 \le K \le 10\).
• Với mọi nhóm không rỗng gồm các thành viên của đảng, có ít nhất một người bất đồng với ít hơn \(K\) người khác trong nhóm đó.

Phân nhóm

Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.

• Nhóm 1 (4 điểm): \(K \le 2\) và \(N \le 5\,000\).
• Nhóm 2 (12 điểm): \(K \le 3\) và \(N \le 5\,000\).
• Nhóm 3 (23 điểm): Mỗi thành viên của đảng bất đồng với nhiều nhất \(10\) thành viên khác, tức là \(D_i \le 10\) với mọi \(0 \le i < N\).
• Nhóm 4 (38 điểm): \(N \le 5\,000\).
• Nhóm 5 (23 điểm): \(K \le 5\).

Ví dụ

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

3

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

2

Nguồn

Baltic Olympiad in Informatics 2017, ngày thi thứ 1.

Vài năm trước, Bộ Cơ sở Hạ tầng Bergen đã chuẩn bị một kế hoạch xây dựng mạng lưới đường sắt nhẹ mới. Mạng lưới này sẽ nối tất cả \(n\) khu dân cư của thành phố bằng \(n-1\) đoạn đường ray, sao cho có đường đi từ bất kỳ khu dân cư nào đến bất kỳ khu dân cư nào khác. Các đoạn đường ray trong kế hoạch được đánh số từ \(1\) đến \(n-1\).

Nhiều năm đã trôi qua, cuộc bầu cử mới đang đến gần, nhưng mạng lưới đường sắt vẫn chỉ tồn tại trên giấy. Vì vậy, Bộ trưởng Bộ Cơ sở Hạ tầng, đại diện cho một đảng rất coi trọng sự bất đồng, quyết định xây dựng ít nhất một phần của kế hoạch. Ông yêu cầu mỗi người trong số \(m\) thứ trưởng chọn những khu dân cư mà họ cho rằng cần được nối với nhau. Từ đó, mỗi thứ trưởng sẽ có một danh sách các đoạn đường ray cần thiết. Nếu một thứ trưởng cho rằng các khu dân cư \(a_1,\ldots,a_s\) cần được nối với nhau, thì theo người đó, các đoạn đường ray cần thiết là tất cả những đoạn nằm trên đường đi trong kế hoạch từ \(a_i\) đến \(a_j\) với ít nhất một cặp chỉ số \(1 \le i < j \le s\).

Bộ trưởng vừa nhận được tất cả các danh sách từ các thứ trưởng. Ông quyết định xây dựng trước những đoạn đường ray được ít nhất \(k\) thứ trưởng yêu cầu. Nhiệm vụ của bạn là lập danh sách những đoạn đường ray này.

Ảnh: Bergen Railway Station, Kamil Porembiński, qua Wikimedia Commons; CC-BY-SA-2.0.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\).

\(n-1\) dòng tiếp theo mô tả kế hoạch. Dòng thứ \(i\) trong số này chứa hai số nguyên \(a_i\) và \(b_i\) (\(1 \le a_i,b_i \le n\), \(a_i \ne b_i\)), cho biết đoạn đường ray thứ \(i\) nối khu dân cư \(a_i\) với khu dân cư \(b_i\).

\(m\) dòng tiếp theo mô tả những khu dân cư được các thứ trưởng lựa chọn. Dòng thứ \(i\) trong số này bắt đầu bằng số nguyên \(s_i\), là số khu dân cư mà thứ trưởng thứ \(i\) chọn, theo sau là \(s_i\) số nguyên chỉ các khu dân cư đó. Tổng độ dài các danh sách không vượt quá \(S\), tức là \(\sum_{i=1}^{m} s_i \le S\).

Dữ liệu ra

Dòng đầu tiên ghi một số nguyên \(r\): số đoạn đường ray được ít nhất \(k\) thứ trưởng yêu cầu.

Dòng thứ hai ghi \(r\) số hiệu của các đoạn đường ray đó theo thứ tự tăng dần.

Ràng buộc

• \(2 \le s_i \le n \le 100\,000\) với mọi \(1 \le i \le m\).
• \(\sum_{i=1}^{m} s_i \le S \le 100\,000\).
• \(1 \le k \le m \le 50\,000\).
• \(1 \le a_i,b_i \le n\) và \(a_i \ne b_i\) với mọi \(1 \le i \le n-1\).
• Mạng lưới trong kế hoạch có \(n-1\) đoạn đường ray và có đường đi giữa mọi cặp khu dân cư.

Phân nhóm

Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.

• Nhóm 1 (8 điểm): \(n \le 10\,000\) và \(S \le 2\,000\).
• Nhóm 2 (15 điểm): \(n \le 10\,000\) và \(m \le 2\,000\).
• Nhóm 3 (7 điểm): Mỗi khu dân cư là đầu mút của nhiều nhất \(2\) đoạn đường ray trong kế hoạch.
• Nhóm 4 (29 điểm): \(k=m\) và \(s_i=2\) với mọi \(1 \le i \le m\).
• Nhóm 5 (16 điểm): \(k=m\).
• Nhóm 6 (25 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

2
2 3

Nguồn

Baltic Olympiad in Informatics 2017, ngày thi thứ 1.

Một công ty vận tải đường bộ muốn tối ưu hóa các quy trình nội bộ, mà chủ yếu là tiết kiệm tiền. Công ty hoạt động trong một vùng mà mỗi con đường đều thu phí. Mỗi con đường nối trực tiếp hai địa điểm, chẳng hạn như thành phố hoặc làng. Công ty xử lý một tập các đơn hàng; mỗi đơn hàng yêu cầu vận chuyển hàng hóa từ một địa điểm đến một địa điểm khác. Khi thực hiện một đơn hàng, công ty muốn trả tổng phí đường bộ nhỏ nhất. Vì mạng lưới đường bộ của vùng có thể được mô hình hóa bằng một đồ thị mà mỗi cạnh có một chi phí cụ thể, chính là phí của con đường tương ứng, điều công ty thực sự muốn biết là chi phí của đường đi rẻ nhất giữa hai đỉnh trong đồ thị này.

Tuy nhiên, đồ thị mạng lưới đường bộ của vùng có một tính chất thú vị: đây là đồ thị có hướng, tức là mọi con đường đều là đường một chiều, và chỉ có thể có cạnh từ \(a\) đến \(b\) nếu \(\left\lfloor b/K \right\rfloor = 1+\left\lfloor a/K \right\rfloor\), với một hằng số \(K\).

Hãy viết chương trình tính, với mỗi đơn hàng trong danh sách được cho, tổng phí đường bộ nhỏ nhất mà công ty phải trả để thực hiện đơn hàng đó.

Ảnh: Wikimedia Commons; CC-BY-SA-3.0.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(K\), \(N\), \(M\) và \(O\), trong đó \(K\) có ý nghĩa như trên, \(N\) là số địa điểm, \(M\) là số con đường và \(O\) là số đơn hàng.

Mỗi dòng trong \(M\) dòng tiếp theo chứa ba số nguyên \(a\), \(b\) và \(t\) (\(0 \le a,b < N\)), cho biết có một con đường một chiều từ \(a\) đến \(b\) với phí \(t\). Dữ liệu bảo đảm \(\left\lfloor b/K \right\rfloor = 1+\left\lfloor a/K \right\rfloor\) và không có hai địa điểm nào được nối bởi nhiều hơn một con đường.

Cuối cùng là \(O\) dòng, mỗi dòng chứa hai số nguyên \(a\) và \(b\), mô tả một đơn hàng vận chuyển hàng hóa từ địa điểm \(a\) đến địa điểm \(b\).

Dữ liệu ra

In ra \(O\) dòng, mỗi dòng chứa một số nguyên. Dòng thứ \(i\) ghi tổng phí trên đường đi rẻ nhất giữa hai địa điểm của đơn hàng thứ \(i\). Nếu không tồn tại đường đi như vậy, in ra \(-1\) trên dòng đó.

Ràng buộc

• \(1 \le N \le 50\,000\).
• \(1 \le O \le 10\,000\).
• \(K \le 5\).
• Với mọi đơn hàng \((a,b)\), \(0 \le a < b < N\).
• Với mọi con đường có phí \(t\), \(1 \le t \le 10\,000\).
• Với mọi con đường từ \(a\) đến \(b\), \(0 \le a,b < N\) và \(\left\lfloor b/K \right\rfloor = 1+\left\lfloor a/K \right\rfloor\).
• Không có hai địa điểm nào được nối bởi nhiều hơn một con đường.

Phân nhóm

Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.

• Nhóm 1 (7 điểm): \(K=1\).
• Nhóm 2 (10 điểm): Mọi đơn hàng đều có \(a=0\).
• Nhóm 3 (8 điểm): \(O \le 100\).
• Nhóm 4 (31 điểm): \(O \le 3\,000\).
• Nhóm 5 (44 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13

15
9
7
8
-1

Nguồn

Baltic Olympiad in Informatics 2017, ngày thi thứ 1.