Đã lâu rồi kể từ lần cuối cùng Pak Dengklek sơn tường cho ngôi nhà của mình, vì vậy anh ấy muốn sơn lại nó. Tường nhà bao gồm \(N\) mảng tường, được đánh số từ \(0\) đến \(N-1\). Trong bài toán này, giả thiết là có \(K\) màu khác nhau, mỗi màu được biểu thị bằng một số nguyên từ \(0\) đến \(K-1\) (ví dụ: màu đỏ được biểu thị bằng \(0\), màu xanh lam được biểu thị bằng \(1\), v.v.). Pak Dengklek muốn sơn mảng tường thứ \(i\) bằng màu \(C[i]\).

Để sơn tường, Pak Dengklek thuê một công ty thầu khoán với \(M\) nhà thầu, được đánh số từ \(0\) đến \(M-1\). Thật không may cho Pak Dengklek, các nhà thầu chỉ sẵn sàng sơn những màu mà họ thích. Cụ thể, nhà thầu thứ \(j\) chỉ thích \(A[j]\) màu và chỉ muốn sơn một mảng tường bằng một trong các màu \(B[j][0], B[j][1], \ldots, B[j][A[j]-1]\).

Pak Dengklek có thể đưa ra một số bản hướng dẫn cho công ty thầu khoán. Với một bản hướng dẫn, Pak Dengklek sẽ đưa ra hai tham số \(x\) và \(y\), trong đó \(0 \le x < M\) và \(0 \le y \le N-M\). Công ty thầu khoán sẽ hướng dẫn nhà thầu thứ \(((x+l) \bmod M)\) sơn mảng tường \((y+l)\) với mọi \(0 \le l < M\). Nếu tồn tại một giá trị \(l\) mà nhà thầu thứ \(((x+l) \bmod M)\) không thích màu \(C[y+l]\), thì bản hướng dẫn này không hợp lệ.

Pak Dengklek phải trả tiền cho mỗi bản hướng dẫn mà anh ta đưa ra, do đó anh ta muốn biết số lượng bản hướng dẫn tối thiểu phải đưa ra để sơn tất cả các mảng tường bằng màu dự kiến ban đầu của chúng, hoặc xác nhận rằng điều đó là không thể. Cùng một mảng tường có thể được sơn nhiều lần, nhưng nó phải luôn được sơn bằng màu dự kiến ban đầu của nó.

Chi tiết cài đặt

Bạn phải cài đặt hàm có chữ ký C++ chính xác như sau:

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B);

Hàm minimumInstructions được trình chấm gọi đúng một lần.

• N: số lượng mảng tường.
• M: số lượng nhà thầu.
• K: số lượng màu sơn.
• C: mảng gồm \(N\) số nguyên biểu diễn màu dự kiến của các mảng tường.
• A: mảng gồm \(M\) số nguyên biểu diễn số lượng màu mà các nhà thầu thích.
• B: mảng gồm \(M\) mảng số nguyên biểu diễn các màu mà các nhà thầu thích; mảng thứ \(j\) có \(A[j]\) phần tử.
• Hàm phải trả về một số nguyên biểu diễn số lượng nhỏ nhất các bản hướng dẫn mà Pak Dengklek phải đưa ra để sơn tất cả các mảng tường bằng màu dự kiến của chúng, hoặc \(-1\) nếu không có phương án thực hiện.

Ví dụ

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

3

Trong ví dụ này, \(N=8\), \(M=3\), \(K=5\), \(C=[3,3,1,3,4,4,2,2]\), \(A=[3,2,2]\) và \(B=[[0,1,2],[2,3],[3,4]]\).

Pak Dengklek có thể đưa ra các bản hướng dẫn như sau:

1. \(x=1\), \(y=0\). Đây là một bản hướng dẫn hợp lệ vì nhà thầu thứ \(1\) có thể sơn mảng tường thứ \(0\), nhà thầu thứ \(2\) có thể sơn mảng tường thứ \(1\), và nhà thầu thứ \(0\) có thể sơn mảng tường thứ \(2\).
2. \(x=0\), \(y=2\). Đây là một bản hướng dẫn hợp lệ vì nhà thầu thứ \(0\) có thể sơn mảng tường thứ \(2\), nhà thầu thứ \(1\) có thể sơn mảng tường thứ \(3\), và nhà thầu thứ \(2\) có thể sơn mảng tường thứ \(4\).
3. \(x=2\), \(y=5\). Đây là một bản hướng dẫn hợp lệ vì nhà thầu thứ \(2\) có thể sơn mảng tường thứ \(5\), nhà thầu thứ \(0\) có thể sơn mảng tường thứ \(6\), và nhà thầu thứ \(1\) có thể sơn mảng tường thứ \(7\).

Dễ dàng thấy rằng Pak Dengklek không thể đưa ra ít hơn \(3\) bản hướng dẫn để sơn toàn bộ các mảng tường, vì vậy minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3, 4]]) trả về \(3\).

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

-1

Trong ví dụ này, \(N=5\), \(M=4\), \(K=4\), \(C=[1,0,1,2,2]\), \(A=[2,1,1,1]\) và \(B=[[0,1],[1],[2],[3]]\). Do nhà thầu thứ \(3\) chỉ thích màu \(3\) và không có mảng tường nào được sơn bằng màu \(3\), Pak Dengklek không thể đưa ra bất kỳ bản hướng dẫn hợp lệ nào. Do đó, minimumInstructions(5, 4, 4, [1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]]) trả về \(-1\).

Ràng buộc

Với \(0 \le k < K\), gọi \(f(k)\) là số lượng chỉ số \(j\) sao cho nhà thầu thứ \(j\) thích màu \(k\). Ví dụ, nếu \(f(1)=2\) thì có hai nhà thầu thích màu \(1\).

• \(1 \le N \le 100\,000\).
• \(1 \le M \le \min(N,50\,000)\).
• \(1 \le K \le 100\,000\).
• \(0 \le C[i] < K\).
• \(1 \le A[j] \le K\).
• \(0 \le B[j][0] < B[j][1] < \ldots < B[j][A[j]-1] < K\).
• Tổng các \(f(k)^2 \le 400\,000\).

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo khuôn dạng sau:

N M K
C[0] C[1] ... C[N-1]
A[0] B[0][0] B[0][1] ... B[0][A[0]-1]
A[1] B[1][0] B[1][1] ... B[1][A[1]-1]
.
.
.
A[M-1] B[M-1][0] B[M-1][1] ... B[M-1][A[M-1]-1]

Trình chấm mẫu in ra giá trị trả về bởi hàm minimumInstructions.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2020: Painting Walls.