Submission #1136364

#TimeUsernameProblemLanguageResultExecution timeMemory
1136364vasyamerAlkemija (COCI18_alkemija)C++20
80 / 80
28 ms9956 KiB
// #pragma comment(linker, "/stack:200000000") // #pragma GCC optimize("Ofast") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4") // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") // #define _GLIBCXX_DEBUG // #define _GLIBCXX_DEBUG_PEDANTIC #include <iomanip> #include <cassert> #include <iostream> #include <vector> #include <random> #include <algorithm> #include <map> #include <set> #include <functional> #include <array> #include <numeric> #include <queue> #include <deque> #include <bitset> #include <cmath> #include <climits> #include <cstdint> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> // using namespace __gnu_pbds; // using namespace __gnu_cxx; using namespace std; const int MOD = 998244353; const long double PI = 3.141592653589793; using ll = long long; const ll INF = 1e18; // #define int ll // --------> sashko123`s defines: #define itn int //Vasya sorry :( #define p_b push_back #define fi first #define se second #define pii std::pair<int, int> #define oo LLONG_MAX #define big INT_MAX #define elif else if int input() { int x; cin >> x; return x; } // ----------> end of sashko123`s defines (thank you Vasya <3) // template<typename K, typename V> // using hash_table = cc_hash_table<K, V, hash<K>>; // template<typename T> // using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; int n, m; const int N = 2e5; vector<int> g[N]; int cnt[N]; int used[N]; void solve() { cin >> n >> m; queue<int> q; for (int i = 0; i < m; i++) { int a; cin >> a; a--; if (used[a] == 0) { used[a] = 1; q.push(a); } } int k; cin >> k; for (int i = 0; i < k; i++) { int L, R; cin >> L >> R; cnt[i + n] = L; while (L--) { int v; cin >> v; v--; g[v].push_back(i + n); } while (R--) { int v; cin >> v; v--; g[i + n].push_back(v); } } while (!q.empty()) { int v = q.front(); q.pop(); for (auto to: g[v]) { cnt[to]--; if (cnt[to] == 0) { for (auto j : g[to]) { if (!used[j]) { q.push(j); used[j] = 1; } } } } } int ans = 0; vector<int> b; for (int i = 0; i < n; i++) { ans += used[i]; if (used[i]) b.push_back(i + 1); } cout << ans << "\n"; for (auto i : b) { cout << i << " "; } } int32_t main(int32_t argc, const char * argv[]) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); // insert code here... int tt= 1; // std::cin >> tt; for (int t = 1; t <= tt; t++) { // cout << "Case #" << t << ": "; solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...