Submission #59126

#	Time	Username	Problem	Language	Result	Execution time	Memory
59126		gusfring	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	626 ms	366540 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
  
const int MAXN = 1e5 + 10;
int N, M;
char inp[MAXN];
char P[MAXN], Q[MAXN];
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;
}
 
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){
         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:31:23: warning: array subscript has type 'char' [-Wchar-subscripts]
       if(p->nxt[V[P[i]]] == NULL) return 0;
                       ^
selling_rna.cpp:32:24: warning: array subscript has type 'char' [-Wchar-subscripts]
       p = p->nxt[V[P[i]]];
                        ^
selling_rna.cpp:38:23: warning: array subscript has type 'char' [-Wchar-subscripts]
       if(s->nxt[V[Q[i]]] == NULL) return 0;
                       ^
selling_rna.cpp:39: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:82:27: warning: array subscript has type 'char' [-Wchar-subscripts]
          int vi = V[inp[j]];
                           ^
selling_rna.cpp:91:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         int vj = V[inp[j]];
                          ^
selling_rna.cpp:76: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:78: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:99: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