Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC Optimaze("Ofast")
- #pragma GCC target("avx,avx2")
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- const int N = 3e4;
- using namespace std;
- using bs = bitset<N>;
- using us = short;
- bs g[N];
- int n;
- bool used[N];
- bool matched[N];
- int mt[N];
- bool Inc(int v) {
- if (used[v]) return false;
- used[v] = true;
- for (auto i = g[v]._Find_first(); i < n; i = g[v]._Find_next(i)) {
- if (mt[i] == -1) {
- matched[v] = true;
- mt[i] = v;
- return true;
- }
- }
- for (auto i = g[v]._Find_first(); i < n; i = g[v]._Find_next(i)) {
- if (Inc(mt[i])) {
- matched[v] = true;
- mt[i] = v;
- return true;
- }
- }
- return false;
- }
- mt19937 rnd(random_device{}());
- int GetMT() {
- memset(matched, 0, sizeof matched);
- fill(mt, mt + N, -1);
- us cur = 0;
- vector<us> indexes(n);
- iota(all(indexes), 0);
- int itr = 0;
- for (us run = 1; run; itr++) {
- run = 0;
- if (itr == 0) {
- sort(all(indexes), [&](int i, int j) {
- return g[i].count() < g[j].count();
- });
- } else {
- shuffle(all(indexes), rnd);
- }
- memset(used, 0, sizeof used);
- for (us i: indexes) {
- if (!matched[i] && Inc(i)) {
- cur++;
- run = 1;
- }
- }
- }
- return cur;
- }
- void solve() {
- cin >> n;
- for (us i = 0; i < n; ++i) {
- us t;
- cin >> t;
- vector<us> haha(t);
- for (us j = 0; j < t; ++j) {
- cin >> haha[j];
- --haha[j];
- }
- g[i].set();
- for (us val: haha) {
- g[val][i] = 0;
- }
- for (us j = n; j < N; j++) {
- g[j][i] = 0;
- }
- }
- GetMT();
- for (us i = 0; i < n; ++i) {
- if (mt[i] == -1) {
- cout << "-1\n";
- return;
- }
- }
- for (int i = 0; i < n; i++) {
- cout << mt[i] + 1 << ' ';
- }
- cout << endl;
- }
- int main() {
- cin.tie(nullptr);
- cout.tie(nullptr);
- ios_base::sync_with_stdio(false);
- us t = 1;
- while (t--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement