oj.uz

Submission #155610

# Submission time Handle Problem Language Result Execution time Memory
155610 2019-09-29T08:32:16 Z georgerapeanu Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 705 ms 154860 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

const int SIGMA = 4;

const int BASE = 5;
const int MOD1 = 1e9 + 7;
const int MOD2 = 666013;

map<char,int> to_norm;

struct hsh_t{
    int h1;
    int h2;
    int len;

    hsh_t(){
        h1 = h2 = len = 0;
    }

    void add_back(int x){
        x++;
        this->len++;
        this->h1 = (1LL * this->h1 * BASE + x) % MOD1;
        this->h2 = (1LL * this->h2 * BASE + x) % MOD2;
    }

    bool operator < (const hsh_t &other)const{
        if(this->h1 != other.h1){
            return this->h1 < other.h1;
        }
        if(this->h2 != other.h2){
            return this->h2 < other.h2;
        }
        return this->len < other.len;
    }
};

struct trie{
    int st,dr;
    int cnt;
    trie *sons[SIGMA];

    trie(){
        st = dr = 0;
        cnt = 0;
        memset(sons,0,sizeof(sons));
    }
} *root;

void ins(trie *root,char *a){
    if(*a == '\0' || *a == '\n'){
        root->cnt++;
        return ;
    }

    if(root->sons[to_norm[(*a)]] == NULL){
        root->sons[to_norm[(*a)]] = new trie();
    }

    ins(root->sons[to_norm[(*a)]],a + 1);
}

vector<pair<hsh_t,int> > pos;

int last = 0;
vector<int> stuff;
void dfs(trie *root){
    root->st = ++last;
    if(root->cnt > 0){
        hsh_t tmp;
        for(int i = (int)stuff.size() - 1;i >= 0;i--){
            tmp.add_back(stuff[i]);
            for(int x = 0;x < root->cnt;x++){
                pos.push_back({tmp,root->st});
            }
        }
    }
    for(int i = 0;i < SIGMA;i++){
        if(root->sons[i] != NULL){
            stuff.push_back(i);
            dfs(root->sons[i]);
            stuff.pop_back();
        }
    }
    root->dr = last;
}

int n,m;
char a[int(1e5) + 5];
char b[int(1e5) + 5];

int get_ans(trie *root,char *a,char *b){
    if(*a != '\n' && *a != '\0'){
        if(root->sons[to_norm[*a]] == NULL){
            return 0;
        }
        return get_ans(root->sons[to_norm[*a]],a + 1,b);
    }

    int len = 0;

    while(b[len] != '\n' && b[len] != '\0'){
        len++;
    }

    len--;

    hsh_t tmp;
    
    while(len >= 0){
        tmp.add_back(to_norm[b[len]]);
        len--;
    }


    return lower_bound(pos.begin(),pos.end(),make_pair(tmp,root->dr + 1)) - lower_bound(pos.begin(),pos.end(),make_pair(tmp,root->st));
}

int main(){

    to_norm['A'] = 0;
    to_norm['C'] = 1;
    to_norm['G'] = 2;
    to_norm['U'] = 3;

    root = new trie();

    scanf("%d %d\n",&n,&m);

    for(int i = 1;i <= n;i++){
        scanf("%s\n",a);
        ins(root,a);
    }

    dfs(root);
    
    sort(pos.begin(),pos.end());
     
    for(int i = 1;i <= m;i++){
        scanf("%s %s\n",a,b);
        printf("%d\n",get_ans(root,a,b));
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s\n",a);
         ~~~~~^~~~~~~~~~
selling_rna.cpp:146:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s %s\n",a,b);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 34316 KB Output is correct
2 Correct 474 ms 34108 KB Output is correct
3 Correct 705 ms 154860 KB Output is correct
4 Correct 702 ms 149068 KB Output is correct
5 Correct 462 ms 109648 KB Output is correct
6 Correct 463 ms 110780 KB Output is correct
7 Correct 407 ms 33600 KB Output is correct
8 Correct 574 ms 78272 KB Output is correct
9 Correct 551 ms 70588 KB Output is correct
10 Correct 491 ms 70212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2668 KB Output is correct
2 Correct 35 ms 2664 KB Output is correct
3 Correct 39 ms 2668 KB Output is correct
4 Correct 29 ms 2664 KB Output is correct
5 Correct 37 ms 2924 KB Output is correct
6 Correct 42 ms 2796 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 472 ms 34316 KB Output is correct
9 Correct 474 ms 34108 KB Output is correct
10 Correct 705 ms 154860 KB Output is correct
11 Correct 702 ms 149068 KB Output is correct
12 Correct 462 ms 109648 KB Output is correct
13 Correct 463 ms 110780 KB Output is correct
14 Correct 407 ms 33600 KB Output is correct
15 Correct 574 ms 78272 KB Output is correct
16 Correct 551 ms 70588 KB Output is correct
17 Correct 491 ms 70212 KB Output is correct
18 Correct 35 ms 2668 KB Output is correct
19 Correct 35 ms 2664 KB Output is correct
20 Correct 39 ms 2668 KB Output is correct
21 Correct 29 ms 2664 KB Output is correct
22 Correct 37 ms 2924 KB Output is correct
23 Correct 42 ms 2796 KB Output is correct
24 Correct 443 ms 34068 KB Output is correct
25 Correct 464 ms 34112 KB Output is correct
26 Correct 438 ms 34052 KB Output is correct
27 Correct 666 ms 132472 KB Output is correct
28 Correct 409 ms 33728 KB Output is correct
29 Correct 178 ms 16980 KB Output is correct