Problem Description
Authorization is an indispensable part of all kinds of business systems. System users obtain the operation rights of each module in the system through authorization mechanism.
The authorization mechanism in this topic is designed as follows: each user has several roles and each role has several privileges. For example, if user david has a manager role and manager role has crm:2 permissions, then user david has crm:2 permissions, that is, the second level permissions of CRM class permissions.
Specifically, usernames and role names are strings of lower-case letters, not more than 32 in length. Permissions can be divided into two categories: hierarchical permissions and non-hierarchical permissions. Hierarchical permissions are composed of permission class names and permission levels, separated by colons ":". The permission class name is also a string of lowercase letters, not more than 32 in length. The permission level is a number. From 0 to 9, the larger the number, the higher the permission level. The system stipulates that if a user has a certain level of authority, then he will automatically have lower levels of authority. For example, in the above example, in addition to crm:2, user david also has crm:1 and crm:0 permissions. Non-hierarchical permissions only have permission class names when describing permissions, and no permission levels (and no colons for separation).
Given the descriptive information of users, roles and rights in the system, your program needs to answer multiple queries about users and rights. Queries can be divided into the following categories:
* Queries without hierarchical permissions: If the permissions themselves are not hierarchical, then the query does not specify the level, returning whether or not it has the permissions;
* Hierarchical query: If the permission itself is hierarchical and the query is hierarchical, it returns whether it has this kind of hierarchical permission or not.
* Non-hierarchical queries with hierarchical permissions: If the permissions themselves are hierarchical and the queries are not hierarchical, they return the level with such permissions; if they do not have any hierarchical permissions of the class, they return "no".
The authorization mechanism in this topic is designed as follows: each user has several roles and each role has several privileges. For example, if user david has a manager role and manager role has crm:2 permissions, then user david has crm:2 permissions, that is, the second level permissions of CRM class permissions.
Specifically, usernames and role names are strings of lower-case letters, not more than 32 in length. Permissions can be divided into two categories: hierarchical permissions and non-hierarchical permissions. Hierarchical permissions are composed of permission class names and permission levels, separated by colons ":". The permission class name is also a string of lowercase letters, not more than 32 in length. The permission level is a number. From 0 to 9, the larger the number, the higher the permission level. The system stipulates that if a user has a certain level of authority, then he will automatically have lower levels of authority. For example, in the above example, in addition to crm:2, user david also has crm:1 and crm:0 permissions. Non-hierarchical permissions only have permission class names when describing permissions, and no permission levels (and no colons for separation).
Given the descriptive information of users, roles and rights in the system, your program needs to answer multiple queries about users and rights. Queries can be divided into the following categories:
* Queries without hierarchical permissions: If the permissions themselves are not hierarchical, then the query does not specify the level, returning whether or not it has the permissions;
* Hierarchical query: If the permission itself is hierarchical and the query is hierarchical, it returns whether it has this kind of hierarchical permission or not.
* Non-hierarchical queries with hierarchical permissions: If the permissions themselves are hierarchical and the queries are not hierarchical, they return the level with such permissions; if they do not have any hierarchical permissions of the class, they return "no".
Input format
The first line of input is a positive integer p, representing the number of different permission categories. The next P line is called a P segment, with a string per line describing each permission. For hierarchical permissions, the format is < category >: < level >, where < category > is the name of permission class and < level > is the highest level of permission. For non-hierarchical permissions, the string contains only the permission class name.
The next line is a positive integer r, representing the number of different roles. The next r line is called the R segment. Each line describes a role in the format of
<role> <s> <privilege 1> <privilege 2> ... <privilege s>
Where < role > is the name of the role and < s > indicates how many permissions the role has. The following < s > strings describe the permissions of the role in the same format as the P segment.
The next line is a positive integer u, representing the number of users. The next U-line is called a U-segment, and each line describes a user in the format of ___________.
<user> <t> <role 1> <role 2> ... <role t>
Where < user > is the user name and < T > indicates how many roles the user has. The following < T > strings describe the user's role.
The next line is a positive integer q, which represents the number of permission queries. The next Q line is called Q segment. Each line describes an authorized query in the form of < user > < privilege >, indicating whether the query user < user > has < privilege > permission. If the permission of the query is hierarchical, the < privilege > in the query can specify the level, indicating whether the query user has the permission of that level or not, indicating that the query user has the level of the permission. For non-hierarchical privileges, only the user can be queried if he has the privilege, and the level can not be specified in the query.
The next line is a positive integer r, representing the number of different roles. The next r line is called the R segment. Each line describes a role in the format of
<role> <s> <privilege 1> <privilege 2> ... <privilege s>
Where < role > is the name of the role and < s > indicates how many permissions the role has. The following < s > strings describe the permissions of the role in the same format as the P segment.
The next line is a positive integer u, representing the number of users. The next U-line is called a U-segment, and each line describes a user in the format of ___________.
<user> <t> <role 1> <role 2> ... <role t>
Where < user > is the user name and < T > indicates how many roles the user has. The following < T > strings describe the user's role.
The next line is a positive integer q, which represents the number of permission queries. The next Q line is called Q segment. Each line describes an authorized query in the form of < user > < privilege >, indicating whether the query user < user > has < privilege > permission. If the permission of the query is hierarchical, the < privilege > in the query can specify the level, indicating whether the query user has the permission of that level or not, indicating that the query user has the level of the permission. For non-hierarchical privileges, only the user can be queried if he has the privilege, and the level can not be specified in the query.
Output format
The output consists of q lines, false, true, or a number for each action. False means that the corresponding user does not have the corresponding permission, true means that the corresponding user has the corresponding permission. For non-hierarchical queries with hierarchical privileges, if they have privileges, the result is a number indicating that the user has the (highest) level of the privilege. If the user does not exist, or the permissions of the query are not defined, then false should be returned.
sample input
3
crm:2
git:3
game
4
hr 1 crm:2
it 3 crm:1 git:1 game
dev 2 git:3 game
qa 1 git:2
3
alice 1 hr
bob 2 it qa
charlie 1 dev
9
alice game
alice crm:2
alice git:0
bob git
bob poweroff
charlie game
charlie crm
charlie git:3
malice game
crm:2
git:3
game
4
hr 1 crm:2
it 3 crm:1 git:1 game
dev 2 git:3 game
qa 1 git:2
3
alice 1 hr
bob 2 it qa
charlie 1 dev
9
alice game
alice crm:2
alice git:0
bob git
bob poweroff
charlie game
charlie crm
charlie git:3
malice game
sample output
false
true
false
2
false
true
false
true
false
true
false
2
false
true
false
true
false
Sample description
In the scenario described by the sample input, the actual permissions of each user are as follows:
* User alice has crm:2 privileges
* User bob has crm:1, git:2 and game permissions
* User charlie has git:3 and game permissions
* User malice is not described and therefore does not have any permissions
* User alice has crm:2 privileges
* User bob has crm:1, git:2 and game permissions
* User charlie has git:3 and game permissions
* User malice is not described and therefore does not have any permissions
Assessment of use case size and conventions
Measure the size of use cases:
* 1 ≤ p, r, u ≤ 100
* 1 ≤ q ≤ 10 000
* Each user has no more than 10 roles, and each role has no more than 10 types of permissions.
Agreements:
* Input guarantees legitimacy, including:
1) The privileges in the list of privileges corresponding to roles (section R) have all appeared before (section P), and the privileges can be repeated. If the privileges with ranks are repeated, the highest level shall prevail.
2) The roles in the user's corresponding roles list (U segment) have all appeared before (R segment). If multiple roles have a certain level of authority, the highest level is the prevailing one.
3) User name and privilege class name in query (Q segment) are not guaranteed to appear before (U segment and P segment)
* The top 20% of test cases have only one role
* 1 ≤ p, r, u ≤ 100
* 1 ≤ q ≤ 10 000
* Each user has no more than 10 roles, and each role has no more than 10 types of permissions.
Agreements:
* Input guarantees legitimacy, including:
1) The privileges in the list of privileges corresponding to roles (section R) have all appeared before (section P), and the privileges can be repeated. If the privileges with ranks are repeated, the highest level shall prevail.
2) The roles in the user's corresponding roles list (U segment) have all appeared before (R segment). If multiple roles have a certain level of authority, the highest level is the prevailing one.
3) User name and privilege class name in query (Q segment) are not guaranteed to appear before (U segment and P segment)
* The top 20% of test cases have only one role
* The first 50% of test case permissions are hierarchical, and queries are not hierarchical.
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
struct P{
char name[33];
int rank;
};
struct R{
char name[33];
vector<P> PofR;
};
struct U{
char name[33];
vector<R> RofU;
};
int main(){
int p,r,u,q;
vector<P> pri;//[100];
vector<R> role;
vector<U> user;
string temp;
cin>>p;//getchar();
//Store p permissions
for(int i=0;i<p;i++){
cin>>temp;
P tempp;
int pos = temp.find(":");
// cout<<"pos="<<pos<<endl;
//No grade
if(pos==-1){
strcpy(tempp.name,temp.c_str());
tempp.rank=-1;
pri.push_back(tempp);
}else{
strcpy(tempp.name,temp.substr(0,pos).c_str());// tempp.name=temp.substr(0,pos);
tempp.rank=temp[pos+1]-48;
pri.push_back(tempp);
}
}
cin>>r;
for(int i=0;i<r;i++){//i roles
R tempr;
role.push_back(tempr);
int num;
// string rname;
// cin>>rname;
cin>>role[i].name;//???
cin>>num;
for(int j=0;j<num;j++){//Receive j permissions
cin>>temp;
int flag=0;
int pos = temp.find(":");
//No grade
if(pos==-1){
//Check whether permissions are duplicated
for(int k=0;k<role[i].PofR.size();k++){
if(strcmp(temp.c_str(),role[i].PofR[k].name)==0){
flag=1;break;
}
}
//No repetition
if(flag==0){
P tempp;
strcpy(tempp.name,temp.c_str());
tempp.rank=-1;
role[i].PofR.push_back(tempp);
}
}
//Graded
else{
int temprank=temp[pos+1]-48;
temp=temp.substr(0,pos);
for(int k=0;k<role[i].PofR.size();k++){
//Repetition
if(strcmp(temp.c_str(),role[i].PofR[k].name)==0){
if(temprank>role[i].PofR[k].rank){
role[i].PofR[k].rank=temprank;//Replace with high-ranking
}
flag=1;break;//continue;
}
}
//No repetition
if(flag==0){
P tempp;
strcpy(tempp.name,temp.c_str());
tempp.rank=temprank;
role[i].PofR.push_back(tempp);
}
}
}
}
cin>>u;
for(int i=0;i<u;i++){
U tempu;
user.push_back(tempu);
cin>>user[i].name;
int num;
cin>>num;
for(int j=0;j<num;j++){
cin>>temp;
for(int k=0;k<role.size();k++){//Find out which RofU is stored in user from role
if(strcmp(temp.c_str(),role[k].name)==0){
user[i].RofU.push_back(role[k]);
break;
}
}
}
}
cin>>q;
for(int i=0;i<q;i++){//i Query
int flag=0;
string username;
string ppp;
int rank=-1;
cin>>username>>ppp;
int pos=ppp.find(":");
if(pos!=-1){
rank=ppp[pos+1]-48;
ppp=ppp.substr(0,pos);
// cout<<"rank!!!="<<rank<<endl;
// cout<<"ppp!!!="<<ppp<<endl;
}
for(int j=0;j<user.size();j++){//j user s
int max=-1;
if(strcmp(username.c_str(),user[j].name)==0){
U tempu=user[j];
for(int k=0;k<tempu.RofU.size();k++){//k role s
R tempr=tempu.RofU[k];
for(int m=0;m<tempr.PofR.size();m++){//m pri s
P tempp=tempr.PofR[m];
if(strcmp(tempp.name,ppp.c_str())==0){//Find this permission
if(tempp.rank==-1){//No grade
cout<<"true"<<endl;
flag=1; //Find out
break;
}else{//Hierarchical Ungraded Query
if(pos==-1){
flag=2;
if(tempp.rank>max) max=tempp.rank;
break;
}else{//Hierarchical and hierarchical queries
if(rank<=tempp.rank){
flag=1;
cout<<"true"<<endl;
break;
}
}
}
}
}
if(flag==2) continue;
if(flag==1) break;
}
if(flag==2){
flag=1;
cout<<max<<endl;
break;
}
if(flag==1) break;
}
if(flag==1) break;
}
if(flag==0) cout<<"false"<<endl;
}
}