oj.uz

Submission #250494

# Submission time Handle Problem Language Result Execution time Memory
250494 2020-07-18T08:15:19 Z parsa_mobed Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1310 ms 1048580 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 5;
int st[N], fn[N], timer;
string s[N];

void convert(string &s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'A') s[i] = 0;
        if (s[i] == 'G') s[i] = 1;
        if (s[i] == 'C') s[i] = 2;
        if (s[i] == 'U') s[i] = 3;
    }
    return ;
}
struct Trie {
    vector <int*> vec = {new int[5]{}};
    inline void addv() {vec.push_back(new int[5]{});}
    inline int* operator [] (int i) {return vec[i];}
    inline void add(string s) {
        int cur = 0;
        for (int i = 0; i < s.size(); i++) {
            if (!vec[cur][(int)s[i]]) vec[cur][(int)s[i]] = vec.size(), vec.push_back(new int[5]{});;
            cur = vec[cur][(int)s[i]];
            vec[cur][4]++;
        }
        return ;
    }
    inline int get(string s) {
        int cur = 0;
        for (int i = 0; i < s.size(); i++) {
            if (!vec[cur][(int)s[i]]) return 0;
            cur = vec[cur][(int)s[i]];
        }
        return cur;
    }
    inline int count(string s) {return vec[get(s)][4];}
} T, seg[N<<2];

void dfs(int v) {
    st[v] = timer++;
    for (int i = 0; i < 4; i++) if (T[v][i]) dfs(T[v][i]);
    fn[v] = timer;
}

void Add(const int &l, const string &s, int L = 0, int R = timer, int id = 1) {
    seg[id].add(s);
    if (R - L == 1) return ;
    int mid = (L+R)>>1;
    if (l < mid) Add(l, s, L, mid, id<<1);
    else Add(l, s, mid, R, id<<1|1);
    return ;
}
int Get(const int &l, const int &r, const string &s, int L = 0, int R = timer, int id = 1) {
    if (r <= L || R <= l) return 0;
    if (l <= L && R <= r) return seg[id].count(s);
    int mid = (L+R)>>1;
    return Get(l, r, s, L, mid, id<<1) + Get(l, r, s, mid, R, id<<1|1);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i], convert(s[i]), T.add(s[i]);
    dfs(0);
    for (int i = 0; i < n; i++) {
        int v = T.get(s[i]);
        reverse(s[i].begin(), s[i].end());
        Add(st[v], s[i]);
    }
    for (int i = 0; i < m; i++){
        string p, q; cin >> p >> q, convert(p), convert(q);
        int v = T.get(p);
        if (v == 0) {cout << 0 << "\n"; continue ;}
        reverse(q.begin(), q.end());
        cout << Get(st[v], fn[v], q) << "\n";
    }
}

Compilation message

selling_rna.cpp: In function 'void convert(std::__cxx11::string&)':
selling_rna.cpp:9:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++) {
                     ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::add(std::__cxx11::string)':
selling_rna.cpp:23:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < s.size(); i++) {
                         ~~^~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::get(std::__cxx11::string)':
selling_rna.cpp:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < s.size(); i++) {
                         ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 751880 KB Output is correct
2 Correct 744 ms 751992 KB Output is correct
3 Correct 747 ms 751864 KB Output is correct
4 Correct 755 ms 751988 KB Output is correct
5 Correct 745 ms 751992 KB Output is correct
6 Correct 741 ms 751992 KB Output is correct
7 Correct 778 ms 751996 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1310 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 752852 KB Output is correct
2 Correct 928 ms 755048 KB Output is correct
3 Correct 814 ms 753912 KB Output is correct
4 Correct 793 ms 752408 KB Output is correct
5 Correct 829 ms 754428 KB Output is correct
6 Correct 831 ms 753784 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 751880 KB Output is correct
2 Correct 744 ms 751992 KB Output is correct
3 Correct 747 ms 751864 KB Output is correct
4 Correct 755 ms 751988 KB Output is correct
5 Correct 745 ms 751992 KB Output is correct
6 Correct 741 ms 751992 KB Output is correct
7 Correct 778 ms 751996 KB Output is correct
8 Runtime error 1310 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -