Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.1 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) begin(a), end(a)
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
const int mod = 998244353;
const int inf = 1e18;
const int MAXN = 1005;

vector<int> Map[MAXN];
set<int> TimeSlotInv[MAXN];
int TimeSlotCnt[MAXN], n, m, r, c;
bitset<MAXN> vis;
bool TimeSlotOpened[MAXN];

void init_every_combination() {
    for (int i = 0; i < n; i++) {
        TimeSlotCnt[i] = 0;
        TimeSlotInv[i].clear();
        TimeSlotOpened[i] = false;
    }
}

bool find(int now) {
    for (auto i : Map[now]) {
        if (!vis[i] && TimeSlotOpened[i]) {
            vis[i] = 1;
            if (TimeSlotCnt[i] < c) {
                TimeSlotCnt[i]++;
                TimeSlotInv[i].insert(now);
                return true;
            } else if (TimeSlotCnt[i] == c) {
                for (auto j : TimeSlotInv[i]) {
                    if (find(j)) {
                        TimeSlotInv[i].insert(now);
                        TimeSlotInv[i].erase(j);
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

void solve() {
    while (cin >> n >> m >> c >> r) {
        for (int i = 0; i < m; i++) {
            int idx, num;
            cin >> idx >> num;
            Map[idx].clear();
            while (num--) {
                int x;
                cin >> x;
                Map[idx].pb(x);
            }
        }
        while (r--) {
            init_every_combination();
            int Tn;
            cin >> Tn;
            for (int i = 0; i < Tn; i++) {
                int x;
                cin >> x;
                TimeSlotOpened[x] = true;
            }
            int ans = m;
            for (int i = 0; i < m; i++) {
                vis.reset();
                if (find(i)) ans--;
            }
            cout << ans << '\n';
        }
    }
}

signed main() {
    cin.sync_with_stdio(0), cin.tie(0);
    int N = 1;
    // cin >> N;
    for (int i = 1; i <= N; i++) {
        solve();
    }
}