OI题库

一天，警官抓获了N个嫌犯，审问N个罪犯的途中，作为警长助手的你突然发现其中被确定为罪犯的K号人是你曾经出生入死的兄弟，你不能眼睁睁看着他被抓进牢里。审问完了嫌犯之后，发现每个人都说话了，并且每个人只说了一句话，说的话形式有两种，“***是罪犯”，“***不是罪犯”，并且罪犯说的都是假话，不是罪犯的说的都是真话(每人说的话均不是说自己)。因为见过某M个人的通缉令，镇长可以确定这M个人是罪犯。通过这些情况可推断出大部分人是不是罪犯。值得庆幸的是，你兄弟并不在这M个人之中。每个人说话的内容都已经存入了资料库之中，现在你需要冒险修改资料库中某些人说话的内容使得你兄弟摆脱的罪犯嫌疑。当然修改的条数越多，风险也就越大，现在希望你能求出最少要修改资料库中几个人说的话。

【输入格式】

第一行，三个整数N，M，K，含义如题目描述所示。

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

第3-N+2行，第i+2行有一个整数X，若X大于零，表示编号为i嫌犯的人说“X号是罪犯”；若X小于零，表示编号i为嫌犯的居民说“-X号不是罪犯”。

【输出格式】

仅一个整数，表示最少需修改资料库中几人说的话。

【样例输入】

3 1 3

1

-2

-3

-1

【样例输出】

2

修改3号说的话和另外随意某人说的话就可以使K号不再是罪犯。

【数据规模】

对于20%的数据，N<=10;

对于100%的数据，N<=200000,1<=M<=N;

数据保证嫌犯说的话不存在矛盾，且K号本为罪犯且未在通缉令上。

 

by kily