oj.uz

Submission #569888

# Submission time Handle Problem Language Result Execution time Memory
569888 2022-05-28T03:57:06 Z cjoa Selling RNA Strands (JOI16_selling_rna) C++11
35 / 100
 214 ms 108760 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 70388 KB Output is correct
2 Correct 185 ms 70380 KB Output is correct
3 Correct 186 ms 71184 KB Output is correct
4 Correct 186 ms 70380 KB Output is correct
5 Correct 195 ms 108760 KB Output is correct
6 Correct 199 ms 108692 KB Output is correct
7 Correct 97 ms 8220 KB Output is correct
8 Correct 214 ms 63148 KB Output is correct
9 Correct 185 ms 59376 KB Output is correct
10 Correct 149 ms 56788 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 189 ms 70388 KB Output is correct
9 Correct 185 ms 70380 KB Output is correct
10 Correct 186 ms 71184 KB Output is correct
11 Correct 186 ms 70380 KB Output is correct
12 Correct 195 ms 108760 KB Output is correct
13 Correct 199 ms 108692 KB Output is correct
14 Correct 97 ms 8220 KB Output is correct
15 Correct 214 ms 63148 KB Output is correct
16 Correct 185 ms 59376 KB Output is correct
17 Correct 149 ms 56788 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -