Submission #58450

#	Time	Username	Problem	Language	Result	Execution time	Memory
58450		ruhanhabib39	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	653 ms	377776 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long Long;

int N, M;
char inp[100 * 1000 + 10];
char P[100 * 1000 + 10], Q[100 * 1000 + 10];
int V[256];
int ii = 0;
int lv = 0;

struct Trie {
   Trie* nxt[4]; Trie* suff; int cc;
   Trie() {
      for(int i = 0; i < 4; i++) {
         nxt[i] = NULL;
      }
   }
   ~Trie() {
      for(int i = 0; i < 4; i++) {
         if(nxt[i]) delete nxt[i];
      }
   }
};

Trie* pref;

int f() {
   Trie *p = pref; int ln = strlen(P);
   for(int i = 0; i < ln; i++) {
      if(p->nxt[V[P[i]]] == NULL) return 0;
      p = p->nxt[V[P[i]]];
   }
   Trie* s = p->suff;
   if(s == NULL) return 0;
   ln = strlen(Q);
   for(int i = ln-1; i >= 0; i--) {
      if(s->nxt[V[Q[i]]] == NULL) return 0;
      s = s->nxt[V[Q[i]]];
   }
   return s->cc;
}

Trie* mix(Trie* a, Trie* b) {
   if(b == NULL) return a;
   if(a == NULL) return b;
   Trie* t = new Trie();
   t->cc = a->cc + b->cc;
   for(int i = 0; i < 4; i++) {
      t->nxt[i] = mix(a->nxt[i], b->nxt[i]);
   }
   return t;
}

// merges the suffixes of trie a, b into a
void merge(Trie* a, Trie* b) {
   if(b == NULL) return;
   if(a->suff == NULL) {
      a->suff = b->suff;
      return;
   }
   if(b->suff == NULL) return;
   a->suff = mix(a->suff, b->suff);
}

void dfs(Trie* t) {
   if(!t) return;
   for(int i = 0; i < 4; i++) {
      dfs(t->nxt[i]);
      merge(t, t->nxt[i]);
   }
}

int main() {
   V['A'] = 0; V['G'] = 1; V['C'] = 2; V['U'] = 3;
   pref = new Trie();
   scanf("%d%d", &N, &M);
   for(int i = 0; i < N; i++) {
      scanf("%s", inp); int ln = strlen(inp);
      Trie* cn = pref;
      for(int j = 0; j < ln; j++) {
         // cerr << "Prefix Adding " << inp[j] << "\n";
         cn->cc++;
         int vi = V[inp[j]];
         if(cn->nxt[vi] == NULL) cn->nxt[vi] = new Trie();
         cn = cn->nxt[vi];
      }
      cn->cc++;
      if(cn->suff == NULL) cn->suff = new Trie();
      Trie* sf = cn->suff;
      for(int j = ln-1; j >= 0; j--) {
         sf->cc++;
         int vj = V[inp[j]];
         if(sf->nxt[vj] == NULL) sf->nxt[vj] = new Trie();
         sf = sf->nxt[vj]; 
      }
      sf->cc++;
   }
   dfs(pref);
   for(int i = 0; i < M; i++) {
      scanf("%s %s", P, Q);
      printf("%d\n", f());
   }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int f()':
selling_rna.cpp:32:23: warning: array subscript has type 'char' [-Wchar-subscripts]
       if(p->nxt[V[P[i]]] == NULL) return 0;
                       ^
selling_rna.cpp:33:24: warning: array subscript has type 'char' [-Wchar-subscripts]
       p = p->nxt[V[P[i]]];
                        ^
selling_rna.cpp:39:23: warning: array subscript has type 'char' [-Wchar-subscripts]
       if(s->nxt[V[Q[i]]] == NULL) return 0;
                       ^
selling_rna.cpp:40:24: warning: array subscript has type 'char' [-Wchar-subscripts]
       s = s->nxt[V[Q[i]]];
                        ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:85:27: warning: array subscript has type 'char' [-Wchar-subscripts]
          int vi = V[inp[j]];
                           ^
selling_rna.cpp:94:27: warning: array subscript has type 'char' [-Wchar-subscripts]
          int vj = V[inp[j]];
                           ^
selling_rna.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &N, &M);
    ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:80:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%s", inp); int ln = strlen(inp);
       ~~~~~^~~~~~~~~~~
selling_rna.cpp:102:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%s %s", P, Q);
       ~~~~~^~~~~~~~~~~~~~~

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