Submission #866797

#TimeUsernameProblemLanguageResultExecution timeMemory
866797txk_2k6Selling RNA Strands (JOI16_selling_rna)C++17
10 / 100
1557 ms478292 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; int n,m; const int mx=1e5+5; const int mxx=2e6+5; string s[mx],s1,s2; struct dl{ set <int> s; int child[5]; }; dl t1[mxx],t2[mxx]; void updn(int j){ t1[j].s={}; for (int i=0;i<5;i++) t1[j].child[i]=-1; } void updn1(int j){ t2[j].s={}; for (int i=0;i<5;i++) t2[j].child[i]=-1; } int p(char s){ if (s=='A') return 1; if (s=='U') return 2; if (s=='G') return 3; if (s=='C') return 4; } void ndl(){ //freopen("RNA.inp","r",stdin); //freopen("RNA.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); } int cnt=0,cnt1=0; void add1(string s,int q){ int u=0,n=s.length(); s=" "+s; for (int i=1;i<=n;i++){ int k=p(s[i]); if (t1[u].child[k]==-1){ updn(++cnt); t1[u].child[k]=cnt; } u=t1[u].child[k]; t1[u].s.insert(q); } } void add2(string s, int q){ int u=0,n=s.length(); s=" "+s; for (int i=n;i>=1;i--){ int k=p(s[i]); if (t2[u].child[k]==-1){ updn1(++cnt1); t2[u].child[k]=cnt1; } u=t2[u].child[k]; t2[u].s.insert(q); } } set <int> se1,se2; int main(){ ndl(); cin >> n >>m; updn(0); updn1(0); for (int i=1;i<=n;i++){ cin >> s[i]; add1(s[i],i); add2(s[i],i); } set <int> :: iterator it,it1; while (m--){ se1={}; se2={}; int kt=0; int res=0; cin >> s1 >> s2; int u=0; for (int i=0;i<s1.length();i++){ int k=p(s1[i]); if (t1[u].child[k]==-1){ cout << 0<<'\n'; kt=1; break; } u=t1[u].child[k]; } if (kt) continue; for (it=t1[u].s.begin();it!=t1[u].s.end();it++){ se1.insert(*it); } u=0; for (int i=s2.length()-1;i>=0;i--){ int k=p(s2[i]); if (t2[u].child[k]==-1){ cout <<0<<'\n'; kt=1; break; } u=t2[u].child[k]; } if (kt) continue; for (it1=t2[u].s.begin();it1!=t2[u].s.end();it1++){ se2.insert(*it1); } it=se1.begin(); it1=se2.begin(); while (it!=se1.end() && it1!=se2.end()){ if (*it==*it1){ it++; it1++; res++; continue; } if (*it<*it1){ it++; continue; } if (*it>*it1){ it1++; continue; } } cout << res<<'\n'; } }

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i=0;i<s1.length();i++){
      |                      ~^~~~~~~~~~~~
selling_rna.cpp: In function 'int p(char)':
selling_rna.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...