Submission #569888

#	Time	Username	Problem	Language	Result	Execution time	Memory
569888		cjoa	Selling RNA Strands (JOI16_selling_rna)	C++11	35 / 100	214 ms	108760 KiB

selling_rna

#include <iostream>

#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <cassert>

using namespace std;

const int MAXN = 5000;
using VI = vector<int>;
using BS = bitset<MAXN>;
//using BS = vector<bool>;

struct Trie {
   struct TrieNode {
      int child[4];
      BS *bs;
      bool shared;
      TrieNode() {
         memset(child, -1, sizeof(child));
         bs = nullptr;
         shared = true;
      }
   };

   vector<TrieNode> nodes;

   static const int root = 0;   // root is at index 0

   Trie() {
   // nodes.reserve(20000);
      nodes.push_back(TrieNode());  // 1st node is root
   }

   void insert(const string& S, int i, int cur, int id) {
      if (i >= int(S.size())) {
         if (nodes[cur].shared) {
            nodes[cur].shared = false;
            nodes[cur].bs = new BS();
            for (int k = 0; k < 4; ++k) {
               int nxt = nodes[cur].child[k];
               if (nxt < 0) continue;
               assert(nodes[nxt].bs != nullptr);
               *nodes[cur].bs |= *nodes[nxt].bs;
            }
         }
         (*nodes[cur].bs)[id] = true;
         return;
      }
      int k = S[i]-'0';
      int nxt = nodes[cur].child[k];
      if (nxt < 0) {
         nxt = nodes[cur].child[k] = nodes.size();
         nodes.push_back(TrieNode());
      }

      insert(S, i+1, nxt, id);

      if (nodes[cur].shared) {
         if (count_if(nodes[cur].child, nodes[cur].child+4,
                      [] (int x) -> bool { return x >= 0 ;} ) > 1) {
            nodes[cur].bs = new BS();
            nodes[cur].shared = false;
            for (int k = 0; k < 4; ++k) {
               int nxt = nodes[cur].child[k];
               if (nxt < 0) continue;
               assert(nodes[nxt].bs != nullptr);
               *nodes[cur].bs |= *nodes[nxt].bs;
            }
         }
         else {
            for (int k = 0; k < 4; ++k) {
               int nxt = nodes[cur].child[k];
               if (nxt < 0) continue;
               nodes[cur].bs = nodes[nxt].bs;
               break;
            }
            if (nodes[cur].bs == nullptr) {
               nodes[cur].bs = new BS();
               nodes[cur].shared = false;
            }
         }
      }
      (*nodes[cur].bs)[id] = true;
   }

   void insert(const string& S, int id) {
      insert(S, 0, root, id);
   }

   BS find(const string& S) {
      int cur = root;
      for (char c : S) {
         int k = c - '0';
         int nxt = nodes[cur].child[k];
         if (nxt < 0)
            return BS();
         cur = nxt;
      }
      return *nodes[cur].bs;
   }
};


const string valid_chars = "ACGU";
void transform(string& S) {
   for (int i = 0; i < (int) S.size(); ++i)
      S[i] = '0' + valid_chars.find( S[i] );
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);

   Trie trie_fwd, trie_rev;

   int N, M;
   cin >> N >> M;

   if (N > 5000) return 0;

   for (int i = 0; i < N; ++i) {
      string chain;
      cin >> chain;
      transform(chain);
      trie_fwd.insert(chain, i);
      reverse(chain.begin(), chain.end());
      trie_rev.insert(chain, i);
   }

   /*
   for (int j = 0; j < (int) trie_fwd.nodes.size(); j++) {
      cerr << j << ": "
           << trie_fwd.nodes[j].shared << ' '
           << trie_fwd.nodes[j].bs << ' '
           << trie_fwd.nodes[j].bs->to_string()
           << endl;
   }
   */

   for (int j = 0; j < M; ++j) {
      string start, end;
      cin >> start >> end;
      transform(start);
      transform(end);
      reverse(end.begin(), end.end());

      BS sf = trie_fwd.find(start);
      BS ef = trie_rev.find(end);
      int res = (sf & ef).count();
      /*
      int res = 0;
      for (int i = 0; i < N; ++i)
         if (sf[i] and ef[i])
            ++res;
      */
      cout << res << '\n';
   }

   return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40