Đề bài

Hằng năm, một triển lãm trò chơi bàn lớn được tổ chức tại Cluj-Napoca, giới thiệu nhiều trò chơi mới. Điểm nhấn chính của năm nay là trò chơi BoardOina.

Có \(n\) người chơi đứng thành một hàng để chờ chơi thử. Họ được đánh số từ \(0\) đến \(n-1\) theo thứ tự trong hàng; người chơi \(0\) đứng đầu hàng và người chơi \(n-1\) đứng cuối hàng.

Có \(m\) quan hệ bạn bè phân biệt giữa \(m\) cặp người chơi. Với mỗi \(i\) từ \(0\) đến \(m-1\), người chơi \(X[i]\) và người chơi \(Y[i]\) là bạn, trong đó \(0\le X[i]<Y[i]<n\). Quan hệ bạn bè có tính đối xứng.

Xét \(k\) người liên tiếp bắt đầu từ người chơi \(s\), với \(0\le s<n\) và \(1\le k\le n-s\). Dãy người chơi này tạo thành một nhóm bạn kích thước \(k\) nếu mọi cặp người trong nhóm đều được nối với nhau bởi một dãy quan hệ bạn bè chỉ đi qua những người thuộc nhóm. Cụ thể, các người chơi \(s,s+1,\ldots,s+k-1\) tạo thành một nhóm bạn nếu với mọi \(u,v\) thỏa mãn \(s\le u<v<s+k\), tồn tại một dãy người chơi \(p[0],\ldots,p[l-1]\) sao cho:

• \(l\ge2\);
• \(s\le p[j]<s+k\) với mọi \(0\le j<l\);
• \(p[0]=u\) và \(p[l-1]=v\);
• \(p[j]\) và \(p[j+1]\) là bạn với mọi \(0\le j<l-1\).

Khi \(k=1\), riêng người chơi \(s\) cũng tạo thành một nhóm bạn kích thước \(1\).

BoardOina có thể được chơi bởi bất kỳ số người nào, nhưng để trò chơi hấp dẫn hơn, ban tổ chức chỉ cho các nhóm bạn tham gia.

Mỗi lần chỉ có một nhóm được chơi. Trong mỗi ván, một nhóm bạn bắt đầu tại người đang đứng đầu hàng được lập ra và bắt đầu chơi; sau đó những người trong nhóm này rời khỏi hàng. Quá trình lặp lại cho đến khi hàng trống.

Nói một cách chính thức, hàng người có thể được chia thành \(g\) nhóm bạn nếu tồn tại mảng kích thước nhóm

thỏa mãn tất cả các điều kiện sau:

• \(g>0\) và \(K[j]>0\) với mọi \(0\le j<g\);
• tổng kích thước các nhóm bằng \(n\):

• với mỗi \(j\) từ \(0\) đến \(g-1\), các người chơi \(s[j],s[j]+1,\ldots,s[j]+K[j]-1\) tạo thành một nhóm bạn kích thước \(K[j]\), trong đó \(s[0]=0\) và, nếu \(j>0\),

Ban tổ chức muốn số nhóm tham gia là nhỏ nhất. Hãy tìm một cách chia hàng thành số nhóm bạn ít nhất và trả về mảng kích thước các nhóm.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> partition_players(
    int n,
    int m,
    std::vector<int> X,
    std::vector<int> Y
);

• n: số người chơi trong hàng.
• m: số quan hệ bạn bè.
• X, Y: hai mảng độ dài \(m\) mô tả các quan hệ bạn bè.
• Hàm phải trả về mảng kích thước các nhóm, biểu diễn một cách chia hàng thành số nhóm bạn ít nhất.
• Hàm được gọi đúng một lần cho mỗi bộ kiểm thử.

Nếu có nhiều cách chia đạt số nhóm ít nhất, bạn có thể trả về bất kỳ cách nào trong số đó.

Ràng buộc

• \(2\le n\le100\,000\).
• \(0\le m\le200\,000\).
• \(0\le X[i]<Y[i]<n\) với mọi \(0\le i<m\).
• Các quan hệ bạn bè đôi một phân biệt: với mọi \(0\le i<j<m\), ta có \(X[i]\ne X[j]\) hoặc \(Y[i]\ne Y[j]\).

Phân nhóm

• Phân nhóm 1 (5 điểm): \(Y[i]=X[i]+1\) với mọi \(0\le i<m\).
• Phân nhóm 2 (7 điểm): \(Y[i]\le X[i]+2\) với mọi \(0\le i<m\).
• Phân nhóm 3 (6 điểm): \(n\le300\) và \(m\le600\).
• Phân nhóm 4 (15 điểm): \(n\le2\,000\) và \(m\le4\,000\).
• Phân nhóm 5 (34 điểm): Không có chu trình quan hệ bạn bè. Cụ thể, với mọi dãy người chơi đôi một phân biệt \(p[0],p[1],\ldots,p[l-1]\) có \(l\ge3\), nếu \(p[j]\) và \(p[j+1]\) là bạn với mọi \(0\le j<l-1\) thì \(p[0]\) và \(p[l-1]\) không phải là bạn.
• Phân nhóm 6 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

partition_players(5, 3, {0, 1, 3}, {1, 4, 4})

{2, 1, 2}

partition_players(7, 6, {0, 4, 2, 1, 2, 3}, {1, 5, 4, 5, 5, 6})

{2, 1, 1, 2, 1}

Trình chấm mẫu

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

• Dòng \(1\): n m.
• Dòng \(2+i\) với \(0\le i<m\): X[i] Y[i].

Gọi mảng do partition_players trả về là \(K[0],K[1],\ldots,K[g-1]\). Trình chấm mẫu in:

• Dòng \(1\): \(g\).
• Dòng \(2\): K[0] K[1] ... K[g-1].