罪犯问题D

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 criminald.in 输出文件 criminald.out

有N个嫌犯,镇长在审问他们,审问过程中不知道哪个人会突然说出来句话,说的话形式有两种,“***是罪犯”,“***不是罪犯”。已知罪犯说的都是假话,不是罪犯的说的都是真话(每人说的话均不指自己)。且因为见过M个人的通缉令,镇长可是确定这M个人是罪犯。通过这些情况可推断出别人是不是罪犯。现在镇长会在审问过程中随时询问作为副手的你,“***是不是罪犯?”,请你设计程序回答“Yes”,“No”或者“Unknown”。

【输入格式】

    第一行,两个整数N,M,含义如题目描述所示。

第二行,M个整数,第i个整数Ti表示编号Ti的嫌犯确定是罪犯。

接下来每行开头有一个大写字母:

若为“S”,表示某嫌犯说话了,接下来有两个整数A,B,若B大于零,表示编号A的嫌犯说“B号是罪犯”;若B小于零,表示编号为A的嫌犯说“-B号不是罪犯”。

若为“A”,表示镇长询问你了,接下来有一个整数X,表示镇长询问你“X号是不是罪犯?”,是则回答“Yes”,不是则回答“No”,在当前已知情况下无法确定则回答“Unknown”。

若为E,表示审问结束。

【输出格式】

假设询问有K个,则输出有K行,对于每一个询问,回答“Yes”,“No”或者“Unknown”。

【样例输入】

3 1

1

A 3

S 1 3

A 3

S 3 -2

A 2

A 1

E

【样例输出】

Unknown

No

No

Yes

【数据规模】

对于30%的数据,N<=1000,S与A数目和<=10000,S:A约为10:3;

对于100%的数据,N<=50000,1<=M<=N, S与A数目和<=200000,S:A约为1:3;

数据保证嫌犯说的话不存在矛盾.

 

by kily