oj.uz

Submission #788046

# Submission time Handle Problem Language Result Execution time Memory
788046 2023-07-19T16:56:02 Z Ahmed57 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 626 ms 865720 KB 
#include<bits/stdc++.h>
using namespace std;
//TRIE
struct node{
   node *nxt[26];
   int cnt = 0;
   node(){
       cnt = 0;
      for(int i = 0;i<26;i++){
        nxt[i] = NULL;
      }
   }
};
struct node2{
   node2 *nxt[26];
   int ma = -1e9 , mi = 1e9;
   node2(){
       ma = -1e9;mi = 1e9;
      for(int i = 0;i<26;i++){
        nxt[i] = NULL;
      }
   }
};
void inser(string w,node *root,node *nroot){
    bool ss = 1;
    for(auto ch:w){
        if(nroot->nxt[ch-'A']==NULL){
            nroot->nxt[ch-'A'] = new node();
        }
        if(ss){
        nroot->cnt = root->cnt;
        for(int i = 0;i<26;i++){
            if(root->nxt[i]==NULL)continue;
            if((ch-'A')!=i)nroot->nxt[i] = root->nxt[i];
        }
        if(root->nxt[ch-'A']==NULL){
            ss = 0;
        }else root = root->nxt[ch-'A'];
        }
        nroot-> cnt++;
        nroot = nroot->nxt[ch-'A'];
    }
    if(ss){
        nroot->cnt = root->cnt;
        for(int i = 0;i<26;i++){
            if(root->nxt[i]==NULL)continue;
            nroot->nxt[i] = root->nxt[i];
        }
    }
    nroot-> cnt++;
}
void inser2(string w,int idx,node2 *root){
    root->ma = max(root->ma,idx);
    root->mi = min(root->mi,idx);
    for(auto ch:w){
        if(root->nxt[ch-'A']==NULL){
            root->nxt[ch-'A'] = new node2();
        }
        root = root->nxt[ch-'A'];
        root->ma = max(root->ma,idx);
        root->mi = min(root->mi,idx);
    }
}
void print(node *root){
    for(int i = 0;i<26;i++){
        if(root->nxt[i]==NULL)continue;
        cout<<char('A'+i)<<","<<root->nxt[i]->cnt<<" ";
        print(root->nxt[i]);
    }
}
node * version[100001];
int serach1(string w,node * r,node * l){
    bool ss = 1;
    for(auto ch:w){
        if(r->nxt[ch-'A']==NULL)return 0;
        r = r->nxt[ch-'A'];
        if(!ss)continue;
        if(l->nxt[ch-'A']==NULL){
            ss = 0;
            continue;
        }else l = l->nxt[ch-'A'];
    }
    if(ss)return r->cnt-l->cnt;
    else return r->cnt;
}
int search2(string w,string lol,node2 * root){
    for(auto ch:w){
        if(root->nxt[ch-'A']==NULL){
            return 0;
        }
        root = root->nxt[ch-'A'];
    }
    int l = root->mi ,r = root->ma;
    if(l>r)return 0;
    return serach1(lol,version[r],version[l-1]);
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<string> v;
    for(int i = 0;i<n;i++){
        string s;cin>>s;
        v.push_back(s);
    }
    sort(v.begin(),v.end());
    version[0] = new node();
    node2 *root = new node2();
    for(int i = 0;i<v.size();i++){
        version[i+1] = new node();
        string xd = v[i];
        reverse(xd.begin(),xd.end());
        inser(xd,version[i],version[i+1]);
        inser2(v[i],i+1,root);
    }
    while(m--){
        string a,b;
        cin>>a>>b;
        reverse(b.begin(),b.end());
        cout<<search2(a,b,root)<<endl;
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 443320 KB Output is correct
2 Correct 318 ms 444304 KB Output is correct
3 Correct 626 ms 865720 KB Output is correct
4 Correct 535 ms 849244 KB Output is correct
5 Correct 356 ms 544196 KB Output is correct
6 Correct 399 ms 552244 KB Output is correct
7 Correct 374 ms 336708 KB Output is correct
8 Correct 454 ms 604788 KB Output is correct
9 Correct 504 ms 576464 KB Output is correct
10 Correct 385 ms 573948 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 35392 KB Output is correct
2 Correct 72 ms 30272 KB Output is correct
3 Correct 96 ms 33184 KB Output is correct
4 Correct 75 ms 31260 KB Output is correct
5 Correct 71 ms 31304 KB Output is correct
6 Correct 100 ms 33532 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 292 ms 443320 KB Output is correct
9 Correct 318 ms 444304 KB Output is correct
10 Correct 626 ms 865720 KB Output is correct
11 Correct 535 ms 849244 KB Output is correct
12 Correct 356 ms 544196 KB Output is correct
13 Correct 399 ms 552244 KB Output is correct
14 Correct 374 ms 336708 KB Output is correct
15 Correct 454 ms 604788 KB Output is correct
16 Correct 504 ms 576464 KB Output is correct
17 Correct 385 ms 573948 KB Output is correct
18 Correct 116 ms 35392 KB Output is correct
19 Correct 72 ms 30272 KB Output is correct
20 Correct 96 ms 33184 KB Output is correct
21 Correct 75 ms 31260 KB Output is correct
22 Correct 71 ms 31304 KB Output is correct
23 Correct 100 ms 33532 KB Output is correct
24 Correct 373 ms 449304 KB Output is correct
25 Correct 567 ms 449604 KB Output is correct
26 Correct 335 ms 449248 KB Output is correct
27 Correct 546 ms 793052 KB Output is correct
28 Correct 546 ms 472796 KB Output is correct
29 Correct 369 ms 248956 KB Output is correct