oj.uz

Submission #59125

# Submission time Handle Problem Language Result Execution time Memory
59125 2018-07-20T15:31:33 Z gusfring Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 21 ms 13228 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long Long;
 
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

selling_rna.cpp: In function 'int f()':
selling_rna.cpp:33:23: warning: array subscript has type 'char' [-Wchar-subscripts]
       if(p->nxt[V[P[i]]] == NULL) return 0;
                       ^
selling_rna.cpp:34:24: warning: array subscript has type 'char' [-Wchar-subscripts]
       p = p->nxt[V[P[i]]];
                        ^
selling_rna.cpp:40:23: warning: array subscript has type 'char' [-Wchar-subscripts]
       if(s->nxt[V[Q[i]]] == NULL) return 0;
                       ^
selling_rna.cpp:41: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:84:27: warning: array subscript has type 'char' [-Wchar-subscripts]
          int vi = V[inp[j]];
                           ^
selling_rna.cpp:93:26: 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:101: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 13048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 13228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 13228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 13048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -