oj.uz

Submission #72342

# Submission time Handle Problem Language Result Execution time Memory
72342 2018-08-26T07:19:41 Z (#2175, xdoju, kazel, pps789) Chocolate Cookie Machine (FXCUP3_chocolate) C++17
28 / 100
 3000 ms 109208 KB 
#include<bits/stdc++.h>
using namespace std;

namespace fio {
    const int BSIZE = 524288;
    char buffer[BSIZE+1];
    int p = BSIZE;
    inline char readChar() {
        if(p == BSIZE) {
            buffer[fread(buffer, 1, BSIZE, stdin)] = '\n';
            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) {
  for(int i : c[x]) {
    ans.erase(i);
  }
}

void boom(int x) {
  if(b[x]) return;
  set<int> nans;
  for(int i : ans) {
    if(c[x].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);
  }
  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);
  }
  if(query.empty()) {
    printf("%d\n",n);
    for(int i=1;i<=n;i++) printf("%d ",i);
    return 0;
  }
  random_shuffle(query.begin(), query.end());
  if(query.back().second) {
    int x = query.back().first;
    for(int i : c[x]) ans.insert(i);
  } else {
    int x = query.back().first;
    for(int i=1;i<=n;i++) if(!b[i]) ans.insert(i);
    for(int i : c[x]) ans.erase(i);
  }
  query.pop_back();
  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);
    } 
  } else {
    for(int i=1;i<=n;i++) {
      if(b[i]) ans.erase(i);
    }
  }
  printf("%zd\n",ans.size());
  for(int i : ans) printf("%d ",i);
  puts("");
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14456 KB Output is correct
2 Correct 18 ms 14528 KB Output is correct
3 Correct 28 ms 15500 KB Output is correct
4 Correct 868 ms 43192 KB Output is correct
5 Correct 17 ms 43192 KB Output is correct
6 Correct 18 ms 43192 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3011 ms 109208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14456 KB Output is correct
2 Correct 18 ms 14528 KB Output is correct
3 Correct 28 ms 15500 KB Output is correct
4 Correct 868 ms 43192 KB Output is correct
5 Correct 17 ms 43192 KB Output is correct
6 Correct 18 ms 43192 KB Output is correct
7 Execution timed out 3011 ms 109208 KB Time limit exceeded
8 Halted 0 ms 0 KB -