• [1339] For Philharmonic

  • 时间限制: 1000 ms　内存限制: 65535 K
  • 问题描述
  • As a ZJUTer, you must need to know that there was a programming team called "Philharmonic" in ZJUT ACM-ICPC history. But why their team named "Philharmonic"? Today, I, MatRush, will tell you the secret.
    As a music fan, xpycc usually love to listen the different kinds of classical music such as symphony and opera. To share his interest with others, he choose the name "Philharmonic" (adj.喜爱音乐的; n.爱乐乐团). Owing to his interest, I made this problem to help him to find his favourtie music.
    Overall there are m singers in music history. Each singer has a personal identifier — an interger from 1 to m (distinct singers have distinct identifiers). As far as I know, xpycc has k favorite singers. He listened the music segments from Internet and wrote the following information for every music: the music title, the number of singers who sang in it, and the identifiers of these singers. Besides, he managed to copy the music titles and how many singers sang there, but he didn't manage to write down the identifiers of some singers. xpycc looks at his records and wonders which musics may be his favourite, and which ones may not be. Once xpycc learns the exact cast of all musics, his favorite musics will be determined as follows: a music becomes favorite music, if no other music from xpycc's list has more favorite singers.
    Now please help xpycc to determine the following for each music:
    whether it surely will be his favourite music;
    whether it surely won't be his favourite music;
    can either be favourite or not.
    作为一个浙江工业大学的学生,你应该得知道曾经有一支"Philharmonic"的队伍在浙江工业大学ACM-ICPC集训队里。但是为什么他们叫"Philharmonic"呢？今天MatRush就来告诉你这个秘密。
    xpycc同学作为一个骨灰级音乐粉丝，经常喜欢欣赏一些不同的古典音乐像交响曲、歌剧等等。为了跟其他的同学分享他的这种爱好，于是我们就把队伍名字定为"Philharmonic"了(adj.喜爱音乐的; n.爱乐乐团). 由于他的这个的兴趣，我就出了这题来帮助他找到他的最爱的音乐。
    问题是这样的：现在一共有m个音乐家在音乐历史上。 每个音乐家都有他的一个个人ID(1<=ID<=m)，并且不同的音乐家有不同的ID。同时我还知道xpycc有k个喜爱的音乐家，同时他经常去互联网上听一些音乐的片段并且给每个片段注释上音乐标题，片段里拥有几个他喜欢的音乐家，以及音乐家ID。但是他忘记了有些音乐家的ID。
    现在xpycc在浏览他听过的歌的记录并且好奇那些音乐是他最喜欢的。（如果某首歌是他最喜欢的，则没有其他的音乐比该音乐含有更多的他喜欢的音乐家。
    现在xpycc把他的听音乐记录给了你，请你帮他确认一下，对于每一首歌：
    1.它一定是他最喜欢的歌。
    2.它一定不可能是他最喜欢的歌。
    3.它可能是他最喜欢的歌也可能不是。
  • 输入
  • There are several cases in this problem.
    For each test case:
    The first line of the input contains two integers m and k (1 ≤ m ≤ 100, 1 ≤ k ≤ m) — the number of singers in total and the number of xpycc's favourite singers.
    The second line contains k distinct integers ai (1 ≤ ai ≤ m) — the identifiers of xpycc's favourite singers.
    The third line contains a single integer n (1 ≤ n ≤ 100) — the number of musics in xpycc's list.
    Then follow n blocks of lines, each block contains a music's description. The i-th music's description contains three lines:
    the first line contains string si (si consists of letters, spaces and digits, and can have the length of from 1 to 20 characters, inclusive) — the music's title,
    the second line contains a non-negative integer di (1 ≤ di ≤ m) — the number of singers who starred in this music,
    the third line has di integers bi, j (0 ≤ bi, j ≤ m) — the identifiers of the singers who star in this music. If bi, j = 0, than xpycc doesn't remember the identifier of the j-th singer. It is guaranteed that the list of singers for a music doesn't contain the same singers.
    All musics have distinct names. The numbers on the lines are separated by single spaces.
    该题有多组数据。对于每组数据：
    第一行是两个整数m和k (1 <= m <= 100, 1 <= k <= m)，表示音乐家总数m以及ycc喜欢的音乐家个数k。
    第二行有k个数ai(1<=i<=k, 1 <=ai <= m)，每一个都表示ycc喜欢的歌手的ID号。
    第三行有一个数n(1 <= n <= 100)，表示ycc听音乐片段的总曲数。
    接下来有n个数据块，每一块的第一行是音乐标题si(si由字母、空格、数字组成，且长度在不超过20)。
    每一块的第二行是一个非负整数di (1 <= di <= m)表示在该个音乐里参与的音乐家数量。
    接下来是di个数，每一个数bj (0 <=bj <= m)，如果它是0，那么表示ycc不记得了第j个参与的音乐家的ID，如果不是0，那么表示第j个参与的音乐家ID是bj，数据保证每一个音乐里不会有2个一样的ID。
    数据包中所有音乐都有不同的名字，且所有数字都以空格分开。
  • 输出
  • For each case, first output "Case #%d:\n", where %d is the id of the case (start from 1).
    Print n lines in the output. In the i-th line print:
    0, if the i-th music will surely be the favourite;
    1, if the i-th music won't surely be the favourite;
    2, if the i-th music can either be favourite, or not favourite.
    Please output an blank line after each case.
    对于每组数据，首先输出Case #%d:\n，其中%d表示是第%d组数据。
    如何接下来有n行，每行是0或1或2。
    0表示第i首音乐一定是xpycc最喜欢的。
    1表示第i首音乐一定不是xpycc最喜欢的。
    2表示第i首音乐可能是xpycc最喜欢的，也可能不是。
  • 样例输入
  • 5 3
1 2 3
6
firstsong
3
0 0 0
secondsong
4
0 0 4 5
thirdsong
1
2
fourthsong
1
5
fifthsong
1
4
sixthsong
2
1 0

5 3
1 3 5
4
Phantom Of The Opera
3
0 0 0
Think Of Me
5
1 2 3 4 0
Fate Symphony
3
2 4 0
Ode to Joy
2
2 4
  • 样例输出
  • Case #1:
2
2
1
1
1
2

Case #2:
2
0
1
1
  • 提示
  • 无
  • 来源
  • Matrush@ZJUT
  • 操作

显示春菜