# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
72367 | 2018-08-26T07:30:50 Z | (#2175, xdoju, kazel, pps789) | Chocolate Cookie Machine (FXCUP3_chocolate) | C++17 | 2750 ms | 124932 KB |
#include<bits/stdc++.h> using namespace std; namespace fio { const int BSIZE = 524288; char buffer[BSIZE]; int p = BSIZE; inline char readChar() { if(p == BSIZE) { fread(buffer, 1, BSIZE, stdin); p = 0; } return buffer[p++]; } int readInt() { char c = readChar(); while (c < '0' || c > '9') { c = readChar(); } int ret = 0; while (c >= '0' && c <= '9') { ret = ret * 10 + c - '0'; c = readChar(); } return ret; } bool isB() { char c = readChar(); while(c != 'B' && c != 'K') c = readChar(); return c == 'B'; } } int n; bool b[300005]; set<int> c[300005], ans; void ok(int x) { if(ans.size() >= c[x].size()) { for(int i : c[x]) { ans.erase(i); } } else { set<int> nans; for(int i : ans) { if(c[x].count(i)) continue; nans.insert(i); } swap(ans, nans); } } void boom(int x) { if(b[x]) return; set<int> nans; if(ans.size() < c[x].size()) { for(int i : ans) { if(c[x].count(i)) nans.insert(i); } } else { for(int i : c[x]) { if(ans.count(i)) nans.insert(i); } } swap(ans,nans); } vector<pair<int,bool>> query; int main() { n = fio::readInt(); int m = fio::readInt(), k = fio::readInt(); for(int i=0;i<m;i++) { int x = fio::readInt(); b[x] = true; } for(int i=0;i<k;i++) { int x = fio::readInt(), y = fio::readInt(); c[y].insert(x); c[x].insert(y); } int minq = 0, minsz = 1e9; bool allb = true; int q = fio::readInt(); for(int i=0;i<q;i++) { int x = fio::readInt(); bool y = fio::isB(); allb &= y; if(y && b[x]) continue; query.emplace_back(x,y); int sz = y ? c[x].size() : (n - c[x].size()); if(sz < minsz) { minsz = sz; minq = query.size() - 1; } } if(query.empty()) { printf("%d\n",n); for(int i=1;i<=n;i++) printf("%d ",i); return 0; } if(query[minq].second) { int x = query[minq].first; for(int i : c[x]) ans.insert(i); } else { int x = query[minq].first; for(int i=1;i<=n;i++) if(!b[i]) ans.insert(i); for(int i : c[x]) ans.erase(i); } swap(query[minq], query.back()); query.pop_back(); random_shuffle(query.begin(), query.end()); for(auto & p : query) { if(p.second) boom(p.first); else ok(p.first); } if(allb) { for(int i=1;i<=n;i++) { if(b[i]) ans.insert(i); } } printf("%zd\n",ans.size()); for(int i : ans) printf("%d ",i); puts(""); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14328 KB | Output is correct |
2 | Correct | 14 ms | 14564 KB | Output is correct |
3 | Correct | 21 ms | 15532 KB | Output is correct |
4 | Correct | 710 ms | 43356 KB | Output is correct |
5 | Correct | 15 ms | 43356 KB | Output is correct |
6 | Correct | 16 ms | 43356 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2750 ms | 109200 KB | Output is correct |
2 | Correct | 120 ms | 109200 KB | Output is correct |
3 | Correct | 499 ms | 109200 KB | Output is correct |
4 | Correct | 1441 ms | 109200 KB | Output is correct |
5 | Correct | 398 ms | 109200 KB | Output is correct |
6 | Correct | 51 ms | 109200 KB | Output is correct |
7 | Correct | 1665 ms | 110596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14328 KB | Output is correct |
2 | Correct | 14 ms | 14564 KB | Output is correct |
3 | Correct | 21 ms | 15532 KB | Output is correct |
4 | Correct | 710 ms | 43356 KB | Output is correct |
5 | Correct | 15 ms | 43356 KB | Output is correct |
6 | Correct | 16 ms | 43356 KB | Output is correct |
7 | Correct | 2750 ms | 109200 KB | Output is correct |
8 | Correct | 120 ms | 109200 KB | Output is correct |
9 | Correct | 499 ms | 109200 KB | Output is correct |
10 | Correct | 1441 ms | 109200 KB | Output is correct |
11 | Correct | 398 ms | 109200 KB | Output is correct |
12 | Correct | 51 ms | 109200 KB | Output is correct |
13 | Correct | 1665 ms | 110596 KB | Output is correct |
14 | Correct | 27 ms | 110596 KB | Output is correct |
15 | Correct | 44 ms | 110596 KB | Output is correct |
16 | Correct | 2217 ms | 113808 KB | Output is correct |
17 | Correct | 546 ms | 113808 KB | Output is correct |
18 | Correct | 1695 ms | 124684 KB | Output is correct |
19 | Correct | 1912 ms | 124684 KB | Output is correct |
20 | Correct | 1927 ms | 124932 KB | Output is correct |
21 | Correct | 2710 ms | 124932 KB | Output is correct |
22 | Correct | 2206 ms | 124932 KB | Output is correct |
23 | Correct | 1863 ms | 124932 KB | Output is correct |