Submission #933050

#	Time	Username	Problem	Language	Result	Execution time	Memory
933050		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	907 ms	1048576 KiB

selling_rna

#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 addword(string s, bool b,lli ind, lli pt){
  for(lli i=ind; i<s.size(); ++i){
    if(b){
    if(trie[pt].next.find({s[i], 0})==trie[pt].next.end()){
      trie[pt].next[{s[i], 0}]=newNode();
    }
    pt=trie[pt].next[{s[i],0}];
    trie[pt].cant++;
    }
    else{
       if(trie[pt].next.find({0,s[i]})==trie[pt].next.end()){
      trie[pt].next[{0,s[i]}]=newNode();
    }
    pt=trie[pt].next[{0,s[i]}];
    trie[pt].cant++;
    }
  }
}

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();
    }
    addword(s, 1, i, pt);
    addword(r, 0, i, pt);
    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({0, q[ind]})!=trie[pt].next.end()){
      ans+=query(p,q, ind+1, trie[pt].next[{0, 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],0})!=trie[pt].next.end()){
      ans+=query(p,q, ind+1, trie[pt].next[{p[ind],0}]);
      }
  
      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 (stderr)

selling_rna.cpp: In function 'void addword(std::string, bool, lli, lli)':
selling_rna.cpp:24:19: 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]
   24 |   for(lli i=ind; i<s.size(); ++i){
      |                  ~^~~~~~~~~
selling_rna.cpp: In function 'void add(std::string)':
selling_rna.cpp:47: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]
   47 |   for(lli i=0; i<s.size(); ++i){
      |                ~^~~~~~~~~
selling_rna.cpp: In function 'lli query(std::string&, std::string&, lli, lli)':
selling_rna.cpp:67: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]
   67 |   if(p.size()<=ind){
      |      ~~~~~~~~^~~~~
selling_rna.cpp:68: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]
   68 |     if(q.size()<=ind){
      |        ~~~~~~~~^~~~~
selling_rna.cpp:72: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]
   72 |       if(ind==q.size()){
      |          ~~~^~~~~~~~~~
selling_rna.cpp:84: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]
   84 |     if(q.size()<=ind){
      |        ~~~~~~~~^~~~~
selling_rna.cpp:85: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]
   85 |          if(ind==p.size()){
      |             ~~~^~~~~~~~~~
selling_rna.cpp:96: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]
   96 |       if(ind==p.size() && ind==q.size()){
      |          ~~~^~~~~~~~~~
selling_rna.cpp:96: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]
   96 |       if(ind==p.size() && ind==q.size()){
      |                           ~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40