// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
using namespace std;
// #define int long long
#define double long double
#define less less228
#define left left228
#define right right228
template<typename T> void uin(T &a, T b) {
if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
if (b > a) a = b;
}
random_device rnd;
template<typename T> void shuffle(vector< T > &v) {
for (int i = 1; i < (int)v.size(); ++i) {
swap(v[rnd() % i], v[i]);
}
for (int i = (int)v.size() - 1; i; --i) {
swap(v[rnd() % i], v[i]);
}
}
const int N = 228228;
int a[N];
struct battle
{
int L, R;
vector<int> x;
vector<int> y;
int value;
battle() {
L = R = value = 0;
x.clear(); y.clear();
}
battle(vector<int> _x, vector<int> _y, int _value) {
L = (int)x.size();
R = (int)y.size();
x = _x;
y = _y;
value = _value;
}
};
bool operator<(battle a, battle b) {
return a.value < b.value;
}
bool operator==(battle a, battle b) {
return a.value == b.value;
}
bool used[N];
battle butt[N];
vector<int> list[N];
bool comp(int i, int j) {
return butt[i] < butt[j] || (butt[i] == butt[j] && i < j);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> a[i];
used[a[i]] = 1;
}
int k;
cin >> k;
auto cmp = [](int a, int b) { return butt[a] < butt[b] || (butt[a] == butt[b] && a < b); };
set<int, decltype(cmp)> st(cmp);
for (int it = 1; it <= k; ++it) {
int L, R;
cin >> L >> R;
vector<int> x(L), y(R);
for (int i = 0; i < L; ++i) {
cin >> x[i];
list[x[i]].push_back(it);
}
for (int i = 0; i < R; ++i) {
cin >> y[i];
}
int value = 0;
for (int X : x) {
value += (!used[X]);
}
butt[it] = battle(x, y, value);
st.insert(it);
}
while (!st.empty()) {
int indx = *st.begin();
st.erase(indx);
if (butt[indx].value > 0) break;
for (int Y : butt[indx].y) {
if (!used[Y]) {
used[Y] = 1;
for (int i : list[Y]) {
if (st.find(i) != st.end()) {
st.erase(i);
butt[i].value--;
st.insert(i);
}
}
}
}
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
cnt += used[i];
}
cout << cnt << endl;
for (int i = 1; i <= n; ++i) {
if (used[i]) {
cout << i << ' ';
}
}
cout << '\n';
return 0;
}
// RU_023
/*
4 2
1 2
2
2 1
1 2
3
2 1
1 3
4
6 3
1 4 5
3
3 2
2 3 4
1 6
1 3
4
1 5 6
1 1
6
2
shironury
boootgslkfjdaojfdopsjfopjso
pgjq]pogjopsjg\qrwjopg
j
pogjqwrjgp]oqwjjqw]pjljfojpjowjow4jgopja ohbip]aeo'rogpoaj0
[bkrw
pипустьбудетрукатвоятвердаojgqwjp\\j\;sync_with_stdiojp
ojeofmpworuc[owejgoprwig
[sdkz
pgj
p[gjes
p0ghjqsp[
jg
prsjgopjg]prwjgoprejgopjrepogjrepog]jgoprejgrgjporeqjgoperjgoprejgopeqrjgopeqrjgoprqwjgpoqjrwsopt4ng\ojsbjsoprnbfqsn\bvhqerpogjorwo
pwewh\rwh \wjiowe orw jop jgr\p jpj o jopj gr\pj p gjop j\pj\pe jp'oj [
k
p[eq fj\pjfdwj\ejopjojopjopjf;'djpfsj, ipojs\p gpsdigsj gorkgjgjrogjdojgiao'fsdvopdshpdfidopcnweojccodj [cjd;ofjd[jdspmcojc"ajno[:Afvoq[w0shbprs`nm/jP{Vadmn;'fnc[Ajojsfpfjcffor 9int i= ; 1 < nfor (int i =1; for (int i =1 ; i <= n: ++i) frfor (int j = 1; j <= ml; ++'}]]]]]]]]]
5
1 5
1 2
2 3
2
4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
19960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
19960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
20068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
19960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
22080 KB |
Output is correct |
| 2 |
Execution timed out |
1033 ms |
22960 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
25064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
27340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
27700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
