Advertisement
999ms

Untitled

Nov 27th, 2021
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.24 KB | None | 0 0
  1. #pragma GCC Optimaze("Ofast")
  2. #pragma GCC target("avx,avx2")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. #define all(x) (x).begin(),(x).end()
  7.  
  8. const int N = 3e4;
  9.  
  10. using namespace std;
  11. using bs = bitset<N>;
  12. using us = short;
  13.  
  14. bs g[N];
  15. int n;
  16. bool used[N];
  17. bool matched[N];
  18. int mt[N];
  19.  
  20. bool Inc(int v) {
  21. if (used[v]) return false;
  22. used[v] = true;
  23. for (auto i = g[v]._Find_first(); i < n; i = g[v]._Find_next(i)) {
  24. if (mt[i] == -1) {
  25. matched[v] = true;
  26. mt[i] = v;
  27. return true;
  28. }
  29. }
  30. for (auto i = g[v]._Find_first(); i < n; i = g[v]._Find_next(i)) {
  31. if (Inc(mt[i])) {
  32. matched[v] = true;
  33. mt[i] = v;
  34. return true;
  35. }
  36. }
  37. return false;
  38. }
  39.  
  40. mt19937 rnd(random_device{}());
  41.  
  42. int GetMT() {
  43. memset(matched, 0, sizeof matched);
  44. fill(mt, mt + N, -1);
  45. us cur = 0;
  46. vector<us> indexes(n);
  47. iota(all(indexes), 0);
  48. int itr = 0;
  49. for (us run = 1; run; itr++) {
  50. run = 0;
  51. if (itr == 0) {
  52. sort(all(indexes), [&](int i, int j) {
  53. return g[i].count() < g[j].count();
  54. });
  55. } else {
  56. shuffle(all(indexes), rnd);
  57. }
  58. memset(used, 0, sizeof used);
  59. for (us i: indexes) {
  60. if (!matched[i] && Inc(i)) {
  61. cur++;
  62. run = 1;
  63. }
  64. }
  65. }
  66. return cur;
  67. }
  68.  
  69. void solve() {
  70. cin >> n;
  71. for (us i = 0; i < n; ++i) {
  72. us t;
  73. cin >> t;
  74. vector<us> haha(t);
  75. for (us j = 0; j < t; ++j) {
  76. cin >> haha[j];
  77. --haha[j];
  78. }
  79. g[i].set();
  80. for (us val: haha) {
  81. g[val][i] = 0;
  82. }
  83. for (us j = n; j < N; j++) {
  84. g[j][i] = 0;
  85. }
  86. }
  87. GetMT();
  88. for (us i = 0; i < n; ++i) {
  89. if (mt[i] == -1) {
  90. cout << "-1\n";
  91. return;
  92. }
  93. }
  94. for (int i = 0; i < n; i++) {
  95. cout << mt[i] + 1 << ' ';
  96. }
  97. cout << endl;
  98. }
  99.  
  100. int main() {
  101. cin.tie(nullptr);
  102. cout.tie(nullptr);
  103. ios_base::sync_with_stdio(false);
  104. us t = 1;
  105. while (t--)
  106. solve();
  107. return 0;
  108. }
  109.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement