问题 2474. -- 华丽の礼

2474: 华丽の礼

时间限制: 0 Sec  内存限制: 128 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

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

输入 [hll.in]

第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)。

输出 [hll.out]

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

样例输入

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

样例输出

3

提示

对于10%的数据,1< =n< =10
对于100%的数据,1< =n< =1000
对于所有的数据,1< =color< =100
a,b< =1000。
【样例解释】
[IMG]http://b24.photo.store.qq.com/http_imgload.cgi?/rurl4_b=f7e587e7f0b018c41620a6de79ee10de684ebcfbe562a0c917e3789ed251c422cfcc2bdeda97d0ae4995dd07abf7335a8b76694ca3d23d17ac501617faed3273c21fe5590e7bdb30f874c10d32b742a6457f26dd[/IMG]
如图即为经过3次染色之后的白纸
其中2=红色  3=黄色  4=绿色
由题意知1可以覆盖颜色1和2
2可以覆盖2和4
3可以覆盖3、2和1
4只能覆盖1
即我们要先用2把颜色4覆盖，再把整张纸覆盖上3.

标签

普及一等 计算几何 图结构 怪盗基德-月下の谜 VIJOS

[上一题][提交][讨论版][状态][下一题]