/ Vijos / 题库 /

华丽の礼

华丽の礼

背景

趁着OIBH组织众小兵对着扑克阵束手无策的时候,基德赶快前进,寻觅传说中的宝石——潘多拉之泪所在的房间。

但是大牛的功力也不是盖的,基德很快了解到,经1009号小兵全力上报,OIBH组织最最令人orz的大牛已经来到扑克阵之前,也许,扑克阵的破解也就是几分钟的事了。

那么,只有抓紧时间了!基德盯着房门,决定尽快进去!

描述

基德终于来到了目标——潘多拉之泪的房间外。而OIBH在房间门口设定了他们的最后一道难题:他们留了一张白纸,以及多种颜色的A染料以及B染料。A染料是万能染料,可以覆盖任何颜色,B染料则只能覆盖一定的颜色。A、B染料都是无限并且齐全的,但是基德只能使用B染料,A染料是机器用的。基德将按下白纸旁的机关,机器会对白纸利用A染料进行N次染色,第i次染以ai,bi为左下角,ci,bi为右上角的区域。基德必须利用B染料把经过机器染色的纸全部染成一种颜色。他现在就站在这张被OIBH进行了N次染色的白纸面前。而他已经知道每种颜色的B染料所能覆盖的颜色。请问,他最终究竟应该把纸染成什么颜色?注意:机器用过的颜色基德才能用,任意一种颜色都能覆盖自己,基德不能用机器没有用过的颜色。当然,白色是可以用的。

[默认白色编号为1,一开始白纸即为白色]

格式

输入格式

第1行3个整数a,b,n。表示机器进行n次染色,白纸的左上角为(0,a),右下角为(b,0)
第2行到第n+1行,每行5个整数,表示ai,bi,ci,di以及此次染色的颜色编号colori。

接下去若干行,每行第一个整数c表示这种颜色的编号,第二个整数p表示它能覆盖的颜色个数,接下去p个整数表示它能覆盖的p种颜色的编号。

设白纸左下角为(0,0)。

输出格式

一个整数,表示最终应该染成的颜色的编号。如果有多解,输出最小的那个。如果无解,输出Escape。

样例1

样例输入1

20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
1 1 2 
2 1 4
3 3 3 2 1
4 1 1

样例输出1

3

提示

对于10%的数据,1<=n<=10
对于100%的数据,1<=n<=1000
对于所有的数据,1<=color<=100
a,b<=1000。

【样例解释】
图片
如图即为经过3次染色之后的白纸
其中2=红色 3=黄色 4=绿色
由题意知1可以覆盖颜色1和2
2可以覆盖2和4
3可以覆盖3、2和1
4只能覆盖1
即我们要先用2把颜色4覆盖,再把整张纸覆盖上3.

信息

ID
1613
难度
7
分类
计算几何 | 图结构 点击显示
标签
递交数
894
已通过
168
通过率
19%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

怪盗基德-月下の谜模拟赛