답안 #59628 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59628	2018-07-22T18:58:39 Z	FLDutchman	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1311 ms	660812 KB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

typedef vector<int> vi;

struct trie{
    vi strings;
    vector<trie*> cld;
    trie(){
        cld.assign(4, 0);
    }
};


int size = 0;

void insert(trie* t, vi &s, int i){
    //cout << i << endl;
    if(i == s.size()){ t->strings.pb(size); return;}
    auto &c = t->cld[s[i]];
    t->strings.pb(size);
    if(!c) c = new trie();
    insert(c, s, i+1);
}

int cnt(trie *t, vi &s, int i, int l, int r){
    if(i == s.size()){
        //cout << "Counting ";
        //for(int k : t->strings) cout << k << " ";
        //cout << endl;
        return lower_bound(t->strings.begin(), t->strings.end(), r) 
             - lower_bound(t->strings.begin(), t->strings.end(), l);
    } else {
        if(!t->cld[s[i]]) return 0;
        return cnt(t->cld[s[i]], s, i+1, l, r);
    }
}

struct modTrie{
    int sz = 0;
    vector<modTrie*> cld;
    int l, r;
    modTrie(){
        cld.assign(16, 0);
    }
};

void insert(modTrie* t, vi &s, int i){
    if(i == s.size()){ t->sz++; return;}
    auto &c = t->cld[s[i]];
    if(!c) c = new modTrie();
    insert(c, s, i+1);
}

trie *T, *revT;

vi S(0), revS(0);
void dfs(modTrie* t){
    t->l = size;
    //cout<<t->sz<<endl;
    for(int i = 0; i < t->sz; i++) {
        insert(T, S, 0);
        insert(revT, revS, 0);
        size++;
    }
    for (int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) if(t->cld[i + 4*j]) {
        S.pb(i); revS.pb(j);
        dfs(t->cld[i + 4*j]);
        S.pop_back(); revS.pop_back();
    }
    t->r = size;
}

void getRange(modTrie* t, vi &s, int i, int &l, int &r){
    if(i == s.size()){
        l = t->l;
        r = t->r;
    } else {
        if(!t->cld[s[i]]){
            l = t->l;
            r = t->l;
        } else getRange(t->cld[s[i]], s, i+1, l, r);
    }
}

int val[300];

int N, M;

modTrie* modT;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    val['A'] = 0;
    val['G'] = 1;
    val['C'] = 2;
    val['U'] = 3;
    cin >> N >> M;
    modT = new modTrie();
    T = new trie();
    revT = new trie();
    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        vi S;
        for(int j = 0; j < s.size(); j++){
            S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
        }
        //cout << "Made S" << endl;
        insert(modT, S, 0);
    }
    dfs(modT);
    //cout << "Done " << endl;

    for(int i = 0; i < M; i++){
        string p, q;
        cin >> p >> q;
        reverse(q.begin(), q.end());
        vi P, Q, S;
        for(char c : p) P.pb(val[c]);
        for(char c : q) Q.pb(val[c]);
        for(int j = 0; j < min(p.size(), q.size()); j++) S.pb(P[j] + 4*Q[j]);
        int l, r;
        getRange(modT, S, 0, l, r);
        //cout << "Range " << l << " " << r << endl;
        //cout << "lowest sz " << S.size() << endl;
        if(P.size() < Q.size()) {
            cout << cnt(revT, Q, 0, l, r) << endl;
        } else cout << cnt(T, P, 0, l, r) << endl;
    }
}




/*

3 3
AA
AA
AGA


*/

Compilation message

selling_rna.cpp: In function 'void insert(trie*, vi&, int)':
selling_rna.cpp:21:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){ t->strings.pb(size); return;}
        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int cnt(trie*, vi&, int, int, int)':
selling_rna.cpp:29:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){
        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'void insert(modTrie*, vi&, int)':
selling_rna.cpp:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){ t->sz++; return;}
        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'void getRange(modTrie*, vi&, int, int&, int&)':
selling_rna.cpp:77:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){
        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:109:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < s.size(); j++){
                        ~~^~~~~~~~~~
selling_rna.cpp:110:27: warning: array subscript has type 'char' [-Wchar-subscripts]
             S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
                           ^
selling_rna.cpp:110:57: warning: array subscript has type 'char' [-Wchar-subscripts]
             S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
                                                         ^
selling_rna.cpp:123:35: warning: array subscript has type 'char' [-Wchar-subscripts]
         for(char c : p) P.pb(val[c]);
                                   ^
selling_rna.cpp:124:35: warning: array subscript has type 'char' [-Wchar-subscripts]
         for(char c : q) Q.pb(val[c]);
                                   ^
selling_rna.cpp:125:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < min(p.size(), q.size()); j++) S.pb(P[j] + 4*Q[j]);
                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	3 ms	548 KB	Output is correct
4	Correct	3 ms	596 KB	Output is correct
5	Correct	3 ms	652 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	3 ms	652 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1221 ms	660812 KB	Output is correct
2	Correct	1095 ms	660812 KB	Output is correct
3	Correct	1311 ms	660812 KB	Output is correct
4	Correct	1160 ms	660812 KB	Output is correct
5	Correct	1250 ms	660812 KB	Output is correct
6	Correct	1014 ms	660812 KB	Output is correct
7	Correct	344 ms	660812 KB	Output is correct
8	Correct	1238 ms	660812 KB	Output is correct
9	Correct	1047 ms	660812 KB	Output is correct
10	Correct	591 ms	660812 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	115 ms	660812 KB	Output is correct
2	Correct	94 ms	660812 KB	Output is correct
3	Correct	102 ms	660812 KB	Output is correct
4	Correct	88 ms	660812 KB	Output is correct
5	Correct	96 ms	660812 KB	Output is correct
6	Correct	104 ms	660812 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	3 ms	548 KB	Output is correct
4	Correct	3 ms	596 KB	Output is correct
5	Correct	3 ms	652 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	3 ms	652 KB	Output is correct
8	Correct	1221 ms	660812 KB	Output is correct
9	Correct	1095 ms	660812 KB	Output is correct
10	Correct	1311 ms	660812 KB	Output is correct
11	Correct	1160 ms	660812 KB	Output is correct
12	Correct	1250 ms	660812 KB	Output is correct
13	Correct	1014 ms	660812 KB	Output is correct
14	Correct	344 ms	660812 KB	Output is correct
15	Correct	1238 ms	660812 KB	Output is correct
16	Correct	1047 ms	660812 KB	Output is correct
17	Correct	591 ms	660812 KB	Output is correct
18	Correct	115 ms	660812 KB	Output is correct
19	Correct	94 ms	660812 KB	Output is correct
20	Correct	102 ms	660812 KB	Output is correct
21	Correct	88 ms	660812 KB	Output is correct
22	Correct	96 ms	660812 KB	Output is correct
23	Correct	104 ms	660812 KB	Output is correct
24	Correct	1227 ms	660812 KB	Output is correct
25	Correct	1304 ms	660812 KB	Output is correct
26	Correct	1219 ms	660812 KB	Output is correct
27	Correct	1210 ms	660812 KB	Output is correct
28	Correct	752 ms	660812 KB	Output is correct
29	Correct	405 ms	660812 KB	Output is correct

답안 #59628

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
40.0 / 40.0