JOI 2019 - Trại huấn luyện, ngày 4

Hôm nay là sinh nhật của IOI-chan. Anh trai của cô bé, JOI-kun, đã đặt trước một chiếc bánh để chúc mừng. Tuy nhiên, cậu đặt nhầm \(N\) miếng bánh thay vì một chiếc bánh nguyên vẹn. Các miếng bánh được đánh số từ \(1\) đến \(N\). Miếng bánh thứ \(i\) có giá trị \(V_i\) và độ đậm màu \(C_i\).

JOI-kun quyết định chọn \(M\) miếng bánh khác nhau trong số \(N\) miếng và xếp chúng thành một vòng tròn. Gọi \(k_1, k_2, \ldots, k_M\) là chỉ số của các miếng bánh theo thứ tự trên vòng tròn, và đặt \(k_{M+1}=k_1\). Vẻ đẹp của cách sắp xếp được định nghĩa là

Hãy tính vẻ đẹp lớn nhất có thể đạt được bằng cách chọn và sắp xếp \(M\) miếng bánh.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N M
V_1 C_1
...
V_N C_N

Dữ liệu ra

In ra một dòng chứa một số nguyên: vẻ đẹp lớn nhất có thể đạt được.

Ràng buộc

• \(3 \le N \le 200\,000\).
• \(3 \le M \le N\).
• \(1 \le V_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le C_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(N \le 100\).
2. \(19\) điểm: \(N \le 2\,000\).
3. \(76\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 3
2 1
4 2
6 4
8 8
10 16

6

8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879

2323231661

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 4 (23/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.

Hợp chúng quốc JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và \(N-1\) đường cao tốc hai chiều, được đánh số từ \(1\) đến \(N-1\). Đường cao tốc thứ \(i\) nối hai thành phố \(A_i\) và \(B_i\). Có thể đi từ một thành phố bất kỳ đến bất kỳ thành phố nào khác bằng các đường cao tốc.

Đất nước có \(K\) bang, được đánh số từ \(1\) đến \(K\). Thành phố thứ \(j\) thuộc bang \(S_j\). Mỗi bang có ít nhất một thành phố.

Đất nước được gọi là có thể chia tách nếu có thể chia toàn bộ các thành phố thành hai nhóm \(X\) và \(Y\) thỏa mãn tất cả các điều kiện sau:

1. Mỗi thành phố thuộc đúng một trong hai nhóm \(X\) và \(Y\).
2. Nhóm \(X\) có ít nhất một thành phố.
3. Nhóm \(Y\) có ít nhất một thành phố.
4. Với mỗi bang, tất cả các thành phố của bang đó thuộc cùng một nhóm.
5. Có thể đi giữa hai thành phố bất kỳ của nhóm \(X\) bằng các đường cao tốc mà chỉ đi qua các thành phố thuộc nhóm \(X\).
6. Có thể đi giữa hai thành phố bất kỳ của nhóm \(Y\) bằng các đường cao tốc mà chỉ đi qua các thành phố thuộc nhóm \(Y\).

Tổng thống K muốn làm cho đất nước không thể chia tách. Để thực hiện điều này, ông có thể tiến hành sáp nhập các bang. Trong một lần sáp nhập, ông chọn hai bang và gộp tất cả các thành phố của hai bang đó thành một bang.

Hãy tính số lần sáp nhập ít nhất để đất nước không thể chia tách. Lưu ý rằng một đất nước chỉ có một bang thì không thể chia tách.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N K
A_1 B_1
...
A_{N-1} B_{N-1}
S_1
...
S_N

Dữ liệu ra

In ra một dòng chứa một số nguyên: số lần sáp nhập ít nhất để đất nước không thể chia tách.

Ràng buộc

• \(1 \le N \le 500\,000\).
• \(1 \le K \le N\).
• \(1 \le A_i,B_i \le N\) với \(1 \le i \le N-1\).
• Có thể đi giữa hai thành phố bất kỳ bằng các đường cao tốc.
• \(1 \le S_j \le K\) với \(1 \le j \le N\).
• Với mỗi \(k\) thỏa mãn \(1 \le k \le K\), tồn tại ít nhất một \(j\) sao cho \(S_j=k\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(10\) điểm: \(N \le 100\), \(K \le 7\).
2. \(24\) điểm: \(N \le 3\,000\).
3. \(14\) điểm: \(N \le 100\,000\), \(K \le 50\).
4. \(22\) điểm: \(N \le 100\,000\). Ban đầu, có thể đi giữa hai thành phố bất kỳ thuộc cùng một bang bằng một đường đi sử dụng không quá \(100\) đường cao tốc.
5. \(30\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

1

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

0

2 2
1 2
1
2

1

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 4 (23/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.

Phòng thí nghiệm của giáo sư JOI đang nghiên cứu \(N\) loại khoáng vật. Mỗi loại có hai lát mẫu, tổng cộng có \(2N\) lát mẫu được đánh số từ \(1\) đến \(2N\).

Một hôm, trợ lý Bitaro làm rơi chiếc hộp đựng các lát mẫu. Cậu không còn biết những lát mẫu nào thuộc cùng một loại khoáng vật.

Phòng thí nghiệm có một thiết bị đo các bước sóng mà khoáng vật hấp thụ, qua đó đếm được số loại khoáng vật khác nhau trong số các lát mẫu đang đặt trong thiết bị. Bitaro muốn xác định \(N\) cặp lát mẫu cùng loại. Ban đầu, thiết bị không chứa lát mẫu nào. Cậu có thể thực hiện các thao tác sau:

• Đưa một lát mẫu vào thiết bị và biết được số loại khoáng vật khác nhau đang có trong thiết bị.
• Lấy một lát mẫu ra khỏi thiết bị và biết được số loại khoáng vật khác nhau đang có trong thiết bị.

Để giáo sư JOI không phát hiện ra sự cố, Bitaro chỉ có thể thực hiện tổng cộng không quá \(1\,000\,000\) thao tác.

Hãy viết chương trình nhận số loại khoáng vật và sử dụng thiết bị để xác định tất cả các cặp lát mẫu cùng loại.

Chi tiết cài đặt

Bạn cần nộp một tệp minerals.cpp, khai báo #include "minerals.h" và cài đặt hàm sau:

void Solve(int N);

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu. Tham số N là số loại khoáng vật.

Chương trình của bạn có thể gọi các hàm sau do trình chấm cung cấp:

int Query(int x);

Hàm này lấy lát mẫu x ra khỏi thiết bị nếu nó đang ở trong thiết bị; ngược lại, đưa lát mẫu đó vào thiết bị. Sau thao tác, hàm trả về số loại khoáng vật khác nhau đang có trong thiết bị.

• Phải có \(1 \le x \le 2N\). Nếu không, chương trình bị đánh giá Wrong Answer [1].
• Không được gọi Query quá \(1\,000\,000\) lần. Nếu vi phạm, chương trình bị đánh giá Wrong Answer [2].

void Answer(int a, int b);

Hàm này thông báo rằng lát mẫu a và lát mẫu b thuộc cùng một loại khoáng vật.

• Phải có \(1 \le a \le 2N\) và \(1 \le b \le 2N\). Nếu không, chương trình bị đánh giá Wrong Answer [3].
• Trong toàn bộ các đối số a và b của tất cả các lần gọi, không giá trị nào được xuất hiện quá một lần. Nếu vi phạm, chương trình bị đánh giá Wrong Answer [4].
• Nếu hai lát mẫu được chỉ định khác loại, chương trình bị đánh giá Wrong Answer [5].
• Phải gọi Answer đúng \(N\) lần. Nếu khi Solve kết thúc mà số lần gọi không bằng \(N\), chương trình bị đánh giá Wrong Answer [6].

Biên dịch và chạy thử

Gói chương trình mẫu gồm trình chấm thử grader.cpp, tệp khai báo minerals.h và tệp mã nguồn mẫu minerals.cpp. Để chạy thử, đặt ba tệp trong cùng một thư mục và biên dịch grader.cpp cùng với minerals.cpp thành chương trình grader.

Dữ liệu vào của trình chấm thử

Trình chấm thử đọc dữ liệu theo định dạng:

N
X_1 Y_1
...
X_N Y_N

Với mỗi \(i\) từ \(1\) đến \(N\), lát mẫu \(X_i\) và lát mẫu \(Y_i\) thuộc cùng một loại khoáng vật.

Dữ liệu ra của trình chấm thử

Khi chương trình kết thúc, trình chấm thử ghi thông tin sau ra đầu ra chuẩn:

• Nếu chương trình của bạn được đánh giá đúng, trình chấm thử ghi số lần gọi Query, chẳng hạn Accepted: 100.
• Nếu chương trình của bạn bị đánh giá sai, trình chấm thử ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình vi phạm nhiều loại lỗi, trình chấm thử chỉ thông báo một loại.

Ràng buộc

Các giá trị \(X_i,Y_i\) được định nghĩa trong phần dữ liệu vào của trình chấm thử.

• \(1 \le N \le 43\,000\).
• \(1 \le X_i \le 2N\) với \(1 \le i \le N\).
• \(1 \le Y_i \le 2N\) với \(1 \le i \le N\).
• \(X_i \ne X_j\) với \(1 \le i < j \le N\).
• \(Y_i \ne Y_j\) với \(1 \le i < j \le N\).
• \(X_i \ne Y_j\) với \(1 \le i \le N\) và \(1 \le j \le N\).

Phân nhóm

1. \(6\) điểm: \(N \le 100\).
2. \(25\) điểm: \(N \le 15\,000\); \(1 \le X_i \le N\) và \(N+1 \le Y_i \le 2N\) với mọi \(1 \le i \le N\).
3. \(9\) điểm: \(N \le 15\,000\).
4. \(30\) điểm: \(N \le 38\,000\).
5. \(5\) điểm: \(N \le 39\,000\).
6. \(5\) điểm: \(N \le 40\,000\).
7. \(5\) điểm: \(N \le 41\,000\).
8. \(5\) điểm: \(N \le 42\,000\).
9. \(10\) điểm: Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Dưới đây là một dữ liệu vào của trình chấm thử và các lời gọi hàm tương ứng.

4
1 5
2 6
3 4
7 8

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 4 (23/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.