Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2014

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2014

Blood Groups

 

By Guilherme Albuquerque Pinto BR Brazil

Timelimit: 1

There are four possible blood groups for humans: AB, A, B and O, meaning that the red blood cells have antigens of types, respectively, A and B, only A, only B, and no antigen at all. Our blood group is determined by two alleles in our DNA. Each allele is of type either A, B or O. The following table lists the possible allele combinations someone may have for each blood group:

We inherit exactly one allele from each of our two parents. So, given the blood groups of the two parents, we can say for sure if some blood group is possible, or not, in their offspring. For example, if the blood groups of the two parents are AB and B, then the possible allele combinations for them are, respectively, {AB} and {OB,BB}. Since the order of the alleles does not matter, the possible allele combinations for the offspring are {OA,AB,OB,BB}. That means the blood groups AB, A and B are possible in their offspring, but the blood group O is not. Very nice indeed! But what if life on Earth had evolved so that a person had three parents, three alleles, and three different antigen types? The allele combinations would look like this:

If the blood groups of the three parents are A, BC and O, then all blood groups are possible in their offspring, except groups BC and ABC. The universe is vast! There may be, out there in space, some form of life whose individuals have N parents, N alleles, and N different antigen types. Given the blood groups for the N parents, and a list of Q blood groups to test, your program has to determine which ones are possible, and which ones are not, in the offspring of the given parents.

 

Input

 

The first line contains two integers N and Q, representing respectively the number of parents (and alleles, and antigen types) and the number of queries (1 ≤ N ≤ 100 and 1 ≤ Q ≤ 40). Each of the next N lines describes the blood group of a parent. After that, each of the next Q lines describes a blood group to test. Antigen types are identified with distinct integers from 1 to N, not letters. Each line describing a blood group contains an integer B indicating the number of antigen types in the blood group (0 ≤ BN), followed by B different integers C1, C2, ..., CB representing the antigen types present in the blood group (1 ≤ CiN for i = 1, 2, ..., B).

 

Output

 

For each of the Q queries, output a line with the uppercase letter “Y” if the corresponding blood group is possible in the offspring of the given parents; otherwise output the uppercase letter “N”. Write the results in the same order that the queries appear in the input.

 

 

 

Input Samples Output Samples

2 1

2 2 1

1 2

0

N

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <:algorithm>:
#include <:cstdio>:
#include <:vector>:
using namespace std;
typedef vector<int> vi;
const int MAXN = 1e3 + 1;
vi pilha[MAXN], vis, match, grafo[MAXN];
int N, Q;
int augmenting_path(int l) {
    if (vis[l]) return 0;
    vis[l] = 1;
    for (int i = 0; i  <  grafo[l].size(); i++) {
        int r = grafo[l][i];
        if (match[r] == -1 || augmenting_path(match[r])) {
            match[r] = l;
            return 1;
        }
    }
    return 0;
}
int main() {
    scanf("%d %d", &N, &Q);
    for (int pai = 1; pai  < = N; pai++) {
        int qtd;
        scanf("%d", &qtd);
        if (qtd != N) pilha[0].push_back(pai);
        while (qtd--) {
            int alelo;
            scanf("%d", &alelo);
            pilha[alelo].push_back(pai);
        }
    }
    while (Q--) {
        for (int i = 1; i  < = N; i++) {
            grafo[i].clear();
        }
        match.assign(N + 1, -1);
        vi possiveis;
        int requer;
        scanf("%d", &requer);
        if (requer != N) possiveis = pilha[0];
        for (int i = 1; i  < = requer; i++) {
            int j;
            scanf("%d", &j);
            for (int k = 0; k  <  pilha[j].size(); k++) {
                grafo[i].push_back(pilha[j][k]);
                possiveis.push_back(pilha[j][k]);
            }
        }
        sort(possiveis.begin(), possiveis.end());
        unique(possiveis.begin(), possiveis.end());
        for (int i = requer + 1; i  < = N; i++) {
            grafo[i] = possiveis;
        }
        int resp = 0;
        for (int i = 1; i  < = N; i++) {
            vis.assign(N + 1, 0);
            resp += augmenting_path(i);
        }
        if (resp == N)
            printf("Y\n");
        else
            printf("N\n");
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2 1
2 2 1
1 2
0

Output

x
+
cmd
14
Advertisements

Demonstration


Previous
#1013 Beecrowd Online Judge Solution 1013 The Greatest Solution in C, C++, Java, Python and C#
Next
#1015 Beecrowd Online Judge Solution 1015 Distance Between Two Points Solution in C, C++, Java, Python and C#