oj.uz

Submission #58450

# Submission time Handle Problem Language Result Execution time Memory
58450 2018-07-17T21:42:21 Z ruhanhabib39 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 653 ms 377776 KB 
#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

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

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 129572 KB Output is correct
2 Correct 199 ms 129572 KB Output is correct
3 Correct 653 ms 377776 KB Output is correct
4 Correct 616 ms 377776 KB Output is correct
5 Correct 327 ms 377776 KB Output is correct
6 Correct 348 ms 377776 KB Output is correct
7 Correct 383 ms 377776 KB Output is correct
8 Correct 501 ms 377776 KB Output is correct
9 Correct 427 ms 377776 KB Output is correct
10 Correct 281 ms 377776 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 377776 KB Output is correct
2 Correct 20 ms 377776 KB Output is correct
3 Correct 19 ms 377776 KB Output is correct
4 Correct 19 ms 377776 KB Output is correct
5 Correct 21 ms 377776 KB Output is correct
6 Correct 21 ms 377776 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 668 KB Output is correct
4 Correct 3 ms 668 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Correct 3 ms 668 KB Output is correct
8 Correct 212 ms 129572 KB Output is correct
9 Correct 199 ms 129572 KB Output is correct
10 Correct 653 ms 377776 KB Output is correct
11 Correct 616 ms 377776 KB Output is correct
12 Correct 327 ms 377776 KB Output is correct
13 Correct 348 ms 377776 KB Output is correct
14 Correct 383 ms 377776 KB Output is correct
15 Correct 501 ms 377776 KB Output is correct
16 Correct 427 ms 377776 KB Output is correct
17 Correct 281 ms 377776 KB Output is correct
18 Correct 22 ms 377776 KB Output is correct
19 Correct 20 ms 377776 KB Output is correct
20 Correct 19 ms 377776 KB Output is correct
21 Correct 19 ms 377776 KB Output is correct
22 Correct 21 ms 377776 KB Output is correct
23 Correct 21 ms 377776 KB Output is correct
24 Correct 209 ms 377776 KB Output is correct
25 Correct 240 ms 377776 KB Output is correct
26 Correct 169 ms 377776 KB Output is correct
27 Correct 491 ms 377776 KB Output is correct
28 Correct 141 ms 377776 KB Output is correct
29 Correct 70 ms 377776 KB Output is correct