This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll val[300];
struct TrieNode
{
int child[4];
int sz;
int bigchild;
vector<int>id,query;
TrieNode()
{
for(int j=0;j<4;j++) child[j]=0;
sz=0;
bigchild=0;
}
};
string s[maxN],a[maxN],b[maxN];
struct Trieu
{
vector<TrieNode>trie;
void kt()
{
trie.pb(TrieNode());
}
void add(int j)
{
ll p=0;
for(int i=0;i<s[j].size();i++)
{
int nxt=val[s[j][i]];
if(trie[p].child[nxt]==0)
{
trie[p].child[nxt]=trie.size();
trie.pb(TrieNode());
}
p=trie[p].child[nxt];
trie[p].sz++;
}
}
void ers(int j)
{
ll p=0;
for(int i=0;i<=s[j].size()-1;i++)
{
int nxt=val[s[j][i]];
if(trie[p].child[nxt]==0)
{
trie[p].child[nxt]=trie.size();
trie.pb(TrieNode());
}
p=trie[p].child[nxt];
trie[p].sz--;
}
}
int query(int j)
{
ll p=0;
for(int i=0;i<=a[j].size()-1;i++)
{
int nxt=val[a[j][i]];
if(trie[p].child[nxt]==0)
{
trie[p].child[nxt]=trie.size();
trie.pb(TrieNode());
}
p=trie[p].child[nxt];
}
return trie[p].sz;
}
}trieu;ll ans[maxN];
struct Triev
{
vector<TrieNode>trie;
void kt()
{
trie.pb(TrieNode());
}
void add(int j)
{
ll p=0;
for(int i=s[j].size()-1;i>=0;i--)
{
int nxt=val[s[j][i]];
if(trie[p].child[nxt]==0)
{
trie[p].child[nxt]=trie.size();
trie.pb(TrieNode());
}
p=trie[p].child[nxt];
}
trie[p].id.push_back(j);
trie[p].sz+=s[j].size();
}
void addq(int j)
{
ll p=0;
for(int i=b[j].size()-1;i>=0;i--)
{
int nxt=val[b[j][i]];
if(trie[p].child[nxt]==0)
{
trie[p].child[nxt]=trie.size();
trie.pb(TrieNode());
}
p=trie[p].child[nxt];
}
trie[p].query.push_back(j);
}
void dfs_sz(int u=0)
{
trie[u].bigchild=-1;
for(int i=0;i<4;i++)
{
int v=trie[u].child[i];
if(v!=0)
{
dfs_sz(v);
trie[u].sz+=trie[v].sz;
int &x=trie[u].bigchild;
if(x==-1||trie[v].sz>trie[x].sz)
{
x=v;
}
}
}
}
void dfs(int u=0,bool keep=1)
{
for(int i=0;i<4;i++)
{
int v=trie[u].child[i];
if(v!=0&&v!=trie[u].bigchild)
{
dfs(v,0);
}
}
if(trie[u].bigchild!=-1)
{
dfs(trie[u].bigchild,1);
int x=trie[u].bigchild;
swap(trie[u].id,trie[x].id);
for(auto zz:trie[x].id) {trie[u].id.pb(zz),trieu.add(zz);}
}
else
{
for(auto zz:trie[u].id)
{
trieu.add(zz);
}
}
for(int i=0;i<4;i++)
{
int v=trie[u].child[i];
if(v!=0&&v!=trie[u].bigchild)
{
for(auto zz:trie[v].id)
{
trie[u].id.pb(zz);
trieu.add(zz);
}
}
}
for(auto zz:trie[u].query)
{
ans[zz]=trieu.query(zz);
//if(u==2) cout << zz<<' ';
}
if(keep==0)
{
for(auto zz:trie[u].id) trieu.ers(zz);
}
}
}trie2;
ll n,m;
void solve()
{
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> s[i];
val['A']=0;
val['U']=1;
val['G']=2;
val['C']=3;
trieu.kt();
trie2.kt();
for(int i=1;i<=m;i++)
{
cin >> a[i] >> b[i];
}
for(int i=1;i<=n;i++)
{
trie2.add(i);
}
for(int i=1;i<=m;i++)
{
trie2.addq(i);
}
trie2.dfs_sz();
trie2.dfs();
for(int i=1;i<=m;i++) cout << ans[i]<<'\n';
}
int main()
{
//fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message (stderr)
selling_rna.cpp: In member function 'void Trieu::add(int)':
selling_rna.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<s[j].size();i++)
| ~^~~~~~~~~~~~
selling_rna.cpp:40:32: warning: array subscript has type 'char' [-Wchar-subscripts]
40 | int nxt=val[s[j][i]];
| ^
selling_rna.cpp: In member function 'void Trieu::ers(int)':
selling_rna.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=0;i<=s[j].size()-1;i++)
| ~^~~~~~~~~~~~~~~
selling_rna.cpp:55:32: warning: array subscript has type 'char' [-Wchar-subscripts]
55 | int nxt=val[s[j][i]];
| ^
selling_rna.cpp: In member function 'int Trieu::query(int)':
selling_rna.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0;i<=a[j].size()-1;i++)
| ~^~~~~~~~~~~~~~~
selling_rna.cpp:70:32: warning: array subscript has type 'char' [-Wchar-subscripts]
70 | int nxt=val[a[j][i]];
| ^
selling_rna.cpp: In member function 'void Triev::add(int)':
selling_rna.cpp:93:32: warning: array subscript has type 'char' [-Wchar-subscripts]
93 | int nxt=val[s[j][i]];
| ^
selling_rna.cpp: In member function 'void Triev::addq(int)':
selling_rna.cpp:109:32: warning: array subscript has type 'char' [-Wchar-subscripts]
109 | int nxt=val[b[j][i]];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |