solution

RBAC nâng cao cho phép các vai trò được tổ chức theo phân cấp (role hierarchy): nếu vai trò $A$ kế thừa vai trò $B$ thì $A$ tự động có tất cả quyền trực tiếp của $B$, và kế thừa này có tính bắc cầu (nếu $A$ kế thừa $B$, $B$ kế thừa $C$ thì $A$ cũng có quyền của $C$). Một vai trò có thể kế thừa nhiều vai trò khác, và đồ thị kế thừa được đảm bảo không có chu trình.

Cho danh sách vai trò cùng quyền trực tiếp (mỗi quyền là một token dạng resource:action), danh sách quan hệ kế thừa, danh sách người dùng (mỗi người dùng được gán đúng một vai trò), và danh sách truy vấn user perm, hãy xác định người dùng có quyền perm hay không (tính cả quyền kế thừa).

Ví dụ

Input:

3
Manager 1 DB:admin
Staff 2 DB:read DB:write
Intern 1 DB:read
2
Manager Staff
Staff Intern
3
Alice Manager
Bob Staff
Cara Intern
5
Alice DB:admin
Alice DB:write
Cara DB:write
Bob DB:read
Dave DB:read

Output:

YES
YES
NO
YES
NO

Giải thích: Alice giữ vai trò Manager, kế thừa Staff và (qua Staff) Intern, nên có cả DB:admin, DB:read, DB:write; Cara chỉ giữ Intern nên không có DB:write; Dave không tồn tại nên bị từ chối.