#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = (int)1e5 + 10;
const int MAXL = (int)2*1e6 + 10;
inline int get(char c){
if(c == 'A') return 0;
else if(c == 'G') return 1;
else if(c == 'C') return 2;
else return 3;
}
string S[MAXN],Q[MAXN];
int Trie[MAXL][4],SZ[MAXL],resposta[MAXN],Trie2[MAXL][4],qtd[MAXL],ptr,ptr2,N,M;
vector<int> folhas[MAXL],queries[MAXL];
vector<int> *cjt[MAXL];
void add_correct(int idx){
int atual = 0;
for(int i = 0;i<S[idx].size();i++){
int c = get(S[idx][i]);
if(Trie[atual][c]){
atual = Trie[atual][c];
}
else{
Trie[atual][c] = ++ptr;
atual = Trie[atual][c];
}
}
folhas[atual].push_back(idx);
}
void add_reverse(int idx){
int atual = 0;
for(int i = 0;i<S[idx].size();i++){
int c = get(S[idx][i]);
if(Trie2[atual][c]){
atual = Trie2[atual][c];
}
else{
Trie2[atual][c] = ++ptr2;
atual = Trie2[atual][c];
}
qtd[atual]++;
}
}
void remove_reverse(int idx){
int atual = 0;
for(int i = 0;i<S[idx].size();i++){
int c = get(S[idx][i]);
if(Trie2[atual][c]){
atual = Trie2[atual][c];
}
qtd[atual]--;
}
}
void query_add(int idx){
int atual = 0;
for(int i = 0;i<Q[idx].size();i++){
int c = get(Q[idx][i]);
if(Trie[atual][c]){
atual = Trie[atual][c];
}
else{
return;
}
}
queries[atual].push_back(idx);
}
int query_reverse(int idx){
int atual = 0;
for(int i = 0;i<Q[idx].size();i++){
int c = get(Q[idx][i]);
if(Trie2[atual][c]){
atual = Trie2[atual][c];
}
else{
return 0;
}
}
return qtd[atual];
}
void calc_sz(int v){
for(int idx : folhas[v]){
SZ[v] += (int)S[idx].size();
}
for(int i = 0;i<4;i++){
if(!Trie[v][i]) continue;
int u = Trie[v][i];
calc_sz(u);
SZ[v] += SZ[u];
}
}
void dfs(int v,int keep){
int mx = -1,big = -1;
for(int i = 0;i<4;i++){
if(!Trie[v][i]) continue;
int u = Trie[v][i];
if(SZ[u] > mx){
mx = SZ[u];
big = u;
}
}
big = -1;
for(int i = 0;i<4;i++){
if(!Trie[v][i]) continue;
int u = Trie[v][i];
if(u == big) continue;
dfs(u,0);
}
if(big != -1){
dfs(big,1);
cjt[v] = cjt[big];
for(int idx : folhas[v]){
cjt[v]->push_back(idx);
add_reverse(idx);
}
}
else{
cjt[v] = new vector<int>();
for(int idx : folhas[v]){
cjt[v]->push_back(idx);
add_reverse(idx);
}
}
for(int i = 0;i<4;i++){
if(!Trie[v][i]) continue;
int u = Trie[v][i];
if(u == big) continue;
for(int idx : *cjt[u]){
cjt[v]->push_back(idx);
add_reverse(idx);
}
}
for(int idx : queries[v]) resposta[idx] = query_reverse(idx);
if(keep == 0){
for(int idx : *cjt[v]){
remove_reverse(idx);
}
}
}
int main(){
cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
scanf("%d %d",&N,&M);
for(int i = 1;i<=N;i++){
cin >> S[i];
add_correct(i);
reverse(S[i].begin(),S[i].end());
}
for(int i = 1;i<=M;i++){
cin >> Q[i];
query_add(i);
cin >> Q[i];
reverse(Q[i].begin(),Q[i].end());
}
calc_sz(0);
dfs(0,1);
for(int i = 1;i<=M;i++){
printf("%d\n",resposta[i]);
}
return 0;
}
Compilation message
selling_rna.cpp: In function 'void add_correct(int)':
selling_rna.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<S[idx].size();i++){
^
selling_rna.cpp: In function 'void add_reverse(int)':
selling_rna.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<S[idx].size();i++){
^
selling_rna.cpp: In function 'void remove_reverse(int)':
selling_rna.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<S[idx].size();i++){
^
selling_rna.cpp: In function 'void query_add(int)':
selling_rna.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<Q[idx].size();i++){
^
selling_rna.cpp: In function 'int query_reverse(int)':
selling_rna.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<Q[idx].size();i++){
^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:141:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
93 ms |
100600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1564 ms |
125476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
114 ms |
125476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
93 ms |
100600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
