Submission #72367

#	Time	Username	Problem	Language	Result	Execution time	Memory
72367		(#118)	Chocolate Cookie Machine (FXCUP3_chocolate)	C++17	100 / 100	2750 ms	124932 KiB

chocolate

#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 (stderr)

chocolate.cpp: In function 'char fio::readChar()':
chocolate.cpp:10:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buffer, 1, BSIZE, stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 28 / 28
• Subtask 2: 55 / 55
• Subtask 3: 17 / 17