Submission #171843

#TimeUsernameProblemLanguageResultExecution timeMemory
171843godwindAlkemija (COCI18_alkemija)C++14
56 / 80
1054 ms29168 KiB
// 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]) { 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 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...