fork download
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. const int INF = (int)1e9+7;
  6.  
  7. int get_mask() {
  8. int P;
  9. cin >> P;
  10. int mask = 0;
  11. for (int i=0; i<P; i++) {
  12. int E;
  13. cin >> E;
  14. mask |= (1<<(E-1));
  15. }
  16. return mask;
  17. }
  18.  
  19. int main() {
  20. ios_base::sync_with_stdio(0);
  21. cin.tie(0); cout.tie(0);
  22. int N, K, Q;
  23. cin >> N >> K >> Q;
  24. vector <pair <int, int>> dp(1<<K, make_pair(INF, -1));
  25. for (int i=0; i<N; i++) {
  26. int C;
  27. cin >> C;
  28. int mask = get_mask();
  29. dp[mask] = min(dp[mask], make_pair(C, i));
  30. }
  31. for (int i=0; i<K; i++) {
  32. for (int mask=0; mask<(1<<K); mask++) {
  33. if (mask & (1<<i)) {
  34. dp[mask ^ (1<<i)] = min(dp[mask ^ (1<<i)], dp[mask]);
  35. }
  36. }
  37. }
  38. for (int i=0; i<Q; i++) {
  39. int car = dp[get_mask()].second;
  40. if (car == -1) cout << "NIE\n";
  41. else cout << (car+1) << "\n";
  42. }
  43. }
  44.  
Success #stdin #stdout 0s 5284KB
stdin
10 5 1
393918786 1
2
383701294 0

239875813 1
1
496573302 4
5 2 4 3
48493338 1
5
370797395 2
4 1
34291848 2
5 3
235525846 5
3 5 1 4 2
98696826 5
2 5 4 3 1
1 5
1 2 3 4 5
1
5
stdout
10