oj.uz

Submission #568258

# Submission time Handle Problem Language Result Execution time Memory
568258 2022-05-25T03:45:40 Z cjoa Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1296 ms 1048576 KB 
#include <iostream>

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

using namespace std;

using BS = bitset<5000>;

struct Trie {
   struct TrieNode {
      int child[4];
      BS prefix;
      TrieNode() {
         memset(child, -1, sizeof(child));
      }
   };

   vector<TrieNode> nodes;

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

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

   void insert(const string& S, int idx) {
      int cur = root;
      nodes[cur].prefix.set(idx);
      for (char c : S) {
         int k = c - '0';
         int nxt = nodes[cur].child[k];
         if (nxt < 0) {
            nxt = nodes.size();
            nodes[cur].child[k] = nxt;
            nodes.push_back(TrieNode());
         }
         cur = nxt;
         nodes[cur].prefix.set(idx);
      }
   }


   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].prefix;
   }
};


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 < 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();
      cout << res << '\n';
   }

   return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1296 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 380 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Runtime error 1296 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -