-
Notifications
You must be signed in to change notification settings - Fork 0
/
2014-blood_groups.cpp
86 lines (70 loc) · 1.87 KB
/
2014-blood_groups.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int>> graph;
int N, Q;
bool visited[200];
int match[200];
bool bpm(graph& g, int u) {
for (int v : g[u])
if (!visited[v]) {
visited[v] = true;
if (match[v] < 0 || bpm(g, match[v])) {
match[v] = u;
return true;
}
}
return false;
}
int max_bipartite_matching(graph& g) {
memset(match, -1, sizeof match);
int result = 0;
for (int u = 0; u < (int)g.size(); u++) {
memset(visited, 0, sizeof visited);
result += bpm(g, u);
}
return result;
}
bool lists_intersect(vector<int>& list, vector<int>& sorted_list) {
for (int item : list)
if (binary_search(sorted_list.begin(), sorted_list.end(), item))
return true;
return false;
}
bool possible(vector<vector<int>> parents, vector<int>& offspring) {
graph g(N);
map<int, vector<int>> antigen_index;
for (int i = 0; i < (int)offspring.size(); i++)
antigen_index[offspring[i]].push_back(i);
for (int i = (int)offspring.size(); i < N; i++) antigen_index[0].push_back(i);
for (int i = 0; i < N; i++)
if (lists_intersect(parents[i], offspring) || (int)parents[i].size() < N)
parents[i].push_back(0);
for (int i = 0; i < N; i++)
for (int j : parents[i])
g[i].insert(g[i].end(), antigen_index[j].begin(), antigen_index[j].end());
return max_bipartite_matching(g) == N;
}
void solve() {
int B, c;
vector<vector<int>> parents(N);
for (int i = 0; i < N; i++) {
scanf("%d", &B);
while (B--) {
scanf("%d", &c);
parents[i].push_back(c);
}
}
while (Q--) {
scanf("%d", &B);
vector<int> offspring;
while (B--) {
scanf("%d", &c);
offspring.push_back(c);
}
sort(offspring.begin(), offspring.end());
printf("%c\n", possible(parents, offspring) ? 'Y' : 'N');
}
}
int main() {
while (scanf("%d %d", &N, &Q) == 2) solve();
}