Editorial for Cuộc họp

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Gọi $new_i$ ~new_i~ là tập các thông tin mà người thứ $i$ ~i~ biết được. Với mỗi cuộc họp, ta giải quyết trong từng trường hợp sau:

Cuộc họp $j$ ~j~ có người đưa tin tham gia: Ta đơn giản bổ sung giá trị $j$ ~j~ vào các tập $new_i$ ~new_i~ nếu người $i$ ~i~ có tham gia cuộc họp.
Cuộc họp $j$ ~j~ không có người đưa tin tham gia: Ta cần xác định $all\_news$ ~all\_news~ là hợp của các tập $new_i$ ~new_i~ với người thứ $i$ ~i~ có tham gia cuộc họp. Việc xây dựng tập $all\_news$ ~all\_news~ có thể thực hiện trong $O(M)$ ~O(M)~. Sau đó, với mỗi người thứ $i$ ~i~ có tham gia cuộc họp, ta cập nhật $new_i=all\_news$ ~new_i=all\_news~.

Độ phức tạp: $O(M^2.N)$ ~O(M^2.N)~

Editorial for Cuộc họp

Comments