oj.uz

Submission #59126

# Submission time Handle Problem Language Result Execution time Memory
59126 2018-07-20T15:32:46 Z gusfring Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 626 ms 366540 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 760 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 126060 KB Output is correct
2 Correct 183 ms 126060 KB Output is correct
3 Correct 592 ms 366540 KB Output is correct
4 Correct 626 ms 366540 KB Output is correct
5 Correct 302 ms 366540 KB Output is correct
6 Correct 285 ms 366540 KB Output is correct
7 Correct 367 ms 366540 KB Output is correct
8 Correct 555 ms 366540 KB Output is correct
9 Correct 502 ms 366540 KB Output is correct
10 Correct 292 ms 366540 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 366540 KB Output is correct
2 Correct 16 ms 366540 KB Output is correct
3 Correct 22 ms 366540 KB Output is correct
4 Correct 14 ms 366540 KB Output is correct
5 Correct 26 ms 366540 KB Output is correct
6 Correct 22 ms 366540 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 181 ms 126060 KB Output is correct
9 Correct 183 ms 126060 KB Output is correct
10 Correct 592 ms 366540 KB Output is correct
11 Correct 626 ms 366540 KB Output is correct
12 Correct 302 ms 366540 KB Output is correct
13 Correct 285 ms 366540 KB Output is correct
14 Correct 367 ms 366540 KB Output is correct
15 Correct 555 ms 366540 KB Output is correct
16 Correct 502 ms 366540 KB Output is correct
17 Correct 292 ms 366540 KB Output is correct
18 Correct 18 ms 366540 KB Output is correct
19 Correct 16 ms 366540 KB Output is correct
20 Correct 22 ms 366540 KB Output is correct
21 Correct 14 ms 366540 KB Output is correct
22 Correct 26 ms 366540 KB Output is correct
23 Correct 22 ms 366540 KB Output is correct
24 Correct 202 ms 366540 KB Output is correct
25 Correct 177 ms 366540 KB Output is correct
26 Correct 195 ms 366540 KB Output is correct
27 Correct 542 ms 366540 KB Output is correct
28 Correct 155 ms 366540 KB Output is correct
29 Correct 64 ms 366540 KB Output is correct