oj.uz

Submission #676455

# Submission time Handle Problem Language Result Execution time Memory
676455 2022-12-31T01:56:36 Z badont Alkemija (COCI18_alkemija) C++17
80 / 80
 135 ms 20532 KB 
#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
LL T;

void solve() {
	LL n, m;
	cin >> n >> m;

	set<LL> v;
	while (m--) {
		LL x; cin >> x;
		x--;
		v.insert(x);
	}

	LL k; cin >> k;
	vector<pair<set<LL>, set<LL>>> a(k);
	vector<vector<LL>> hit(n);
	F0R (i, k) {
		auto& [s1, s2] = a[i];
		LL l, r;
		cin >> l >> r;
		while (l--) {
			LL x; cin >> x; x--;
			if (!v.count(x)) {
				s1.insert(x);
				hit[x].pb(i);
			}
		}

		while (r--) {
			LL x; cin >> x; x--;
			s2.insert(x);
		}
	}

	queue<LL> rmv;
	F0R (i, k) {
		if (a[i].f.empty()) {
			rmv.push(i);
		} 
	}

	vector<LL> visitedSet(k);
	while (!rmv.empty()) {
		LL g = rmv.front();
		rmv.pop();
		if (visitedSet[g])
			continue;
		visitedSet[g] = true;

		auto& [s1, s2] = a[g];
		assert(s1.empty());

		for (auto u : s2) if (!v.count(u)) {
			v.insert(u);
			for (auto z : hit[u]) {
				if (a[z].f.count(u)) {
					a[z].f.erase(u);
					if (a[z].f.empty()) {
						rmv.push(z);
					}
				}
			}
		}
		s2.clear();
	}

	vector<LL> ans;
	for (auto u : v)ans.pb(u);

	cout << ans.size() << '\n';
	F0R (i, (int)ans.size()) 
		cout << ans[i] + 1 << " \n"[i == (int)ans.size() - 1];

}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6092 KB Output is correct
2 Correct 47 ms 8012 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 13164 KB Output is correct
2 Correct 108 ms 15448 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 19628 KB Output is correct
2 Correct 80 ms 13852 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 20460 KB Output is correct
2 Correct 127 ms 20532 KB Output is correct