oj.uz

Submission #933047

# Submission time Handle Problem Language Result Execution time Memory
933047 2024-02-24T23:11:56 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 233456 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) ;
using lli=long long int;
 
 
#ifndef LOCAL
    #define endl '\n'
#endif
 
struct Node{
  map<pair<char,char>, lli> next;
  lli cant=0;
};
vector<Node> trie;
lli currNode=0;
lli newNode(){
  trie.pb(Node());
  return currNode++;
}

void add(string s){
  lli pt=0;

  string r=s;
  reverse(r.begin(), r.end());
  for(lli i=0; i<s.size(); ++i){
    deb(i);
    trie[pt].cant++;
    if(trie[pt].next.find({s[i], r[i]})==trie[pt].next.end()){
      trie[pt].next[{s[i], r[i]}]=newNode();
    }
    pt=trie[pt].next[{s[i], r[i]}];

  }
  trie[pt].cant++;
}


lli query(string &p, string &q, lli ind, lli pt){
  deb(p);
  deb(q);
  deb(ind);
  deb(pt);
  if(p.size()<=ind){
    if(q.size()<=ind){
      return trie[pt].cant;
    }
    else{
      if(ind==q.size()){
        return trie[pt].cant;
      }
      lli ans=0;
      if(trie[pt].next.find({'A', q[ind]})!=trie[pt].next.end()){
        ans+=query(p,q, ind+1, trie[pt].next[{'A', q[ind]}]);
      }
      if(trie[pt].next.find({'U', q[ind]})!=trie[pt].next.end()){
        ans+=query(p,q, ind+1, trie[pt].next[{'U', q[ind]}]);
      }
      if(trie[pt].next.find({'G', q[ind]})!=trie[pt].next.end()){
        ans+=query(p,q, ind+1, trie[pt].next[{'G', q[ind]}]);
      }
      if(trie[pt].next.find({'C', q[ind]})!=trie[pt].next.end()){
        ans+=query(p,q, ind+1, trie[pt].next[{'C', q[ind]}]);
      }
      return ans;
    }
  }
  else{
    if(q.size()<=ind){
         if(ind==p.size()){
        return trie[pt].cant;
      }
      lli ans=0;
      if(trie[pt].next.find({ p[ind],'A'})!=trie[pt].next.end()){
        ans+=query(p,q, ind+1, trie[pt].next[{p[ind],'A'}]);
      }
     if(trie[pt].next.find({ p[ind],'U'})!=trie[pt].next.end()){
        ans+=query(p,q, ind+1, trie[pt].next[{p[ind],'U'}]);
      }
      if(trie[pt].next.find({ p[ind],'G'})!=trie[pt].next.end()){
        ans+=query(p,q, ind+1, trie[pt].next[{p[ind],'G'}]);
      }
      if(trie[pt].next.find({ p[ind],'C'})!=trie[pt].next.end()){
        ans+=query(p,q, ind+1, trie[pt].next[{p[ind],'C'}]);
      }
      return ans;
    }
    else{
      if(ind==p.size() && ind==q.size()){
        return trie[pt].cant;
      }
      lli ans=0;
      if(trie[pt].next.find({p[ind],q[ind] })!=trie[pt].next.end()){
        ans+=query(p,q,ind+1, trie[pt].next[{p[ind], q[ind]}]);
      }
      return ans;
    }
  }
}

void solve(){
    lli n;
    lli m;
    cin>>n>>m;
    newNode();
    deb(n);
    for(lli i=0; i<n; ++i){
      deb(i);
      string s;
      cin>>s;
      deb(s);
      add(s);
    }
    for(lli i=0; i<m; ++i){
      string p,q;
      cin>>p>>q;
      reverse(q.begin(), q.end());
      lli ans=query(p,q,0,0);
      cout<<ans<<endl;
    }

}
 
 
int main(){
  ios::ios_base::sync_with_stdio(0);
  cin.tie(0);
  #ifdef LOCAL
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
  #endif
  lli t=1;
//  cin>>t;
  while(t--){
    
    solve();

  }
}

Compilation message

selling_rna.cpp: In function 'void add(std::string)':
selling_rna.cpp:28:17: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(lli i=0; i<s.size(); ++i){
      |                ~^~~~~~~~~
selling_rna.cpp: In function 'lli query(std::string&, std::string&, lli, lli)':
selling_rna.cpp:46:14: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'long long int'} [-Wsign-compare]
   46 |   if(p.size()<=ind){
      |      ~~~~~~~~^~~~~
selling_rna.cpp:47:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'long long int'} [-Wsign-compare]
   47 |     if(q.size()<=ind){
      |        ~~~~~~~~^~~~~
selling_rna.cpp:51:13: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |       if(ind==q.size()){
      |          ~~~^~~~~~~~~~
selling_rna.cpp:71:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'long long int'} [-Wsign-compare]
   71 |     if(q.size()<=ind){
      |        ~~~~~~~~^~~~~
selling_rna.cpp:72:16: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |          if(ind==p.size()){
      |             ~~~^~~~~~~~~~
selling_rna.cpp:91:13: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       if(ind==p.size() && ind==q.size()){
      |          ~~~^~~~~~~~~~
selling_rna.cpp:91:30: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       if(ind==p.size() && ind==q.size()){
      |                           ~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1578 ms 233456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 600 KB Output is correct
2 Correct 48 ms 1116 KB Output is correct
3 Correct 33 ms 856 KB Output is correct
4 Correct 11 ms 584 KB Output is correct
5 Correct 46 ms 1312 KB Output is correct
6 Correct 38 ms 856 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Execution timed out 1578 ms 233456 KB Time limit exceeded
9 Halted 0 ms 0 KB -