oj.uz

답안 #788037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788037 2023-07-19T16:48:18 Z Ahmed57 Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 319 ms 443044 KB 
#include<bits/stdc++.h>
using namespace std;
//TRIE
struct node{
   node *nxt[26];
   int cnt = 0;
   node(){
       cnt = 0;
      for(int i = 0;i<26;i++){
        nxt[i] = NULL;
      }
   }
};
struct node2{
   node2 *nxt[26];
   int ma = -1e9 , mi = 1e9;
   node2(){
       ma = -1e9;mi = 1e9;
      for(int i = 0;i<26;i++){
        nxt[i] = NULL;
      }
   }
};
void inser(string w,node *root,node *nroot){
    bool ss = 1;
    for(auto ch:w){
        if(nroot->nxt[ch-'A']==NULL){
            nroot->nxt[ch-'A'] = new node();
        }
        if(ss){
        for(int i = 0;i<26;i++){
            if(root->nxt[i]==NULL)continue;
            if((ch-'A')!=i)nroot->nxt[i] = root->nxt[i];
            nroot->cnt+=root->nxt[i]->cnt;
        }
        if(root->nxt[ch-'A']==NULL){
            ss = 0;
        }else root = root->nxt[ch-'A'];
        }
        nroot-> cnt++;
        nroot = nroot->nxt[ch-'A'];
    }
    nroot->cnt++;
}
void inser2(string w,int idx,node2 *root){
    root->ma = max(root->ma,idx);
    root->mi = min(root->mi,idx);
    for(auto ch:w){
        if(root->nxt[ch-'A']==NULL){
            root->nxt[ch-'A'] = new node2();
        }
        root = root->nxt[ch-'A'];
        root->ma = max(root->ma,idx);
        root->mi = min(root->mi,idx);
    }
}
void print(node *root){
    for(int i = 0;i<26;i++){
        if(root->nxt[i]==NULL)continue;
        cout<<char('A'+i)<<","<<root->nxt[i]->cnt<<" ";
        print(root->nxt[i]);
    }
}
node * version[100001];
int serach1(string w,node * r,node * l){
    bool ss = 1;
    for(auto ch:w){
        if(r->nxt[ch-'A']==NULL)return 0;
        r = r->nxt[ch-'A'];
        if(!ss)continue;
        if(l->nxt[ch-'A']==NULL){
            ss = 0;
            continue;
        }else l = l->nxt[ch-'A'];
    }
    if(ss)return r->cnt-l->cnt;
    else return r->cnt;
}
int search2(string w,string lol,node2 * root){
    for(auto ch:w){
        if(root->nxt[ch-'A']==NULL){
            return 0;
        }
        root = root->nxt[ch-'A'];
    }
    int l = root->mi ,r = root->ma;
    if(l>r)return 0;
    return serach1(lol,version[r],version[l-1]);
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<string> v;
    for(int i = 0;i<n;i++){
        string s;cin>>s;
        v.push_back(s);
    }
    sort(v.begin(),v.end());
    version[0] = new node();
    node2 *root = new node2();
    for(int i = 0;i<v.size();i++){
        version[i+1] = new node();
        string xd = v[i];
        reverse(xd.begin(),xd.end());
        inser(xd,version[i],version[i+1]);
        inser2(v[i],i+1,root);
    }
    while(m--){
        string a,b;
        cin>>a>>b;
        reverse(b.begin(),b.end());
        cout<<search2(a,b,root)<<endl;
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 319 ms 443044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 108 ms 35356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -