oj.uz

Submission #752798

# Submission time Handle Problem Language Result Execution time Memory
752798 2023-06-03T21:13:25 Z racsosabe Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 152 ms 196560 KB 
#include<bits/stdc++.h>
using namespace::std;
 
const int N = 100000 + 5;
const int SUML = 2000000 + 5;
const int E = 4;
const string alphabet = "AGCU";

int id(char c) {
    for(int i = 0; i < alphabet.size(); i++) {
        if(alphabet[i] == c) return i;
    }
    assert(false);
}

int n;
int m;
int T = 1;
int nodes;
int in[N];
int out[N];
int res[N];
string s[N];
string Q[N];
int sorted[N];
int frec[SUML];
int trie[E][SUML];
vector<int> ids[SUML];
vector<int> pending[N];

void add_node() {
    for(int i = 0; i < E; i++) trie[i][nodes] = 0;
    frec[nodes] = 0;
    ids[nodes].clear();
    nodes += 1;
}

void insert(string &s, int to) {
    int pos = 0;
    for(int i = 0; i < s.size(); i++) {
        int c = id(s[i]);
        if(trie[c][pos] == 0) {
            trie[c][pos] = nodes;
            add_node();
        }
        pos = trie[c][pos];
        frec[pos] += 1;
    }
    ids[pos].emplace_back(to);
}

void sort_strings(int u = 0) {
    in[u] = T;
    for(auto x : ids[u]) {
        sorted[T++] = x;
    }
    for(int c = 0; c < E; c++) {
        if(!trie[c][u]) continue;
        sort_strings(trie[c][u]);
    }
    out[u] = T - 1;
}

int query(string &s) {
    int pos = 0;
    for(int i = 0; i < s.size(); i++) {
        int c = id(s[i]);
        if(!trie[c][pos]) return 0;
        pos = trie[c][pos];
    }
    return frec[pos];
}

void solve() {
    nodes = 0;
    add_node();
    for(int i = 1; i < T; i++) {
        insert(s[sorted[i]], 0);
        for(auto to : pending[i]) {
            if(to < 0) {
                res[-to] -= query(Q[-to]);
            }
            else { 
                res[to] += query(Q[to]);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    nodes = 1;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
        insert(s[i], i);
    }
    sort_strings();
    for(int i = 1; i <= m; i++) {
        string P;
        cin >> P >> Q[i];
        reverse(Q[i].begin(), Q[i].end());
        int pos = 0;
        for(int j = 0; j < P.size(); j++) {
            int c = id(P[j]);
            if(!trie[c][pos]) {
                pos = -1;
                break;
            }
            pos = trie[c][pos];
        }
        if(~pos) {
            pending[in[pos] - 1].emplace_back(-i);
            pending[out[pos]].emplace_back(i);
        }
    }
    for(int i = 1; i <= n; i++) reverse(s[i].begin(), s[i].end());
    solve();
    for(int i = 1; i <= m; i++) cout << res[i] << '\n';
	return 0;
}

Compilation message

selling_rna.cpp: In function 'int id(char)':
selling_rna.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i = 0; i < alphabet.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void insert(std::string&, int)':
selling_rna.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int query(std::string&)':
selling_rna.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int j = 0; j < P.size(); j++) {
      |                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55892 KB Output is correct
2 Correct 26 ms 55928 KB Output is correct
3 Correct 26 ms 55868 KB Output is correct
4 Correct 28 ms 55896 KB Output is correct
5 Correct 29 ms 55888 KB Output is correct
6 Correct 27 ms 55892 KB Output is correct
7 Correct 26 ms 55892 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 100752 KB Output is correct
2 Correct 139 ms 98788 KB Output is correct
3 Runtime error 152 ms 196560 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 57960 KB Output is correct
2 Correct 44 ms 57292 KB Output is correct
3 Correct 45 ms 57764 KB Output is correct
4 Correct 42 ms 57276 KB Output is correct
5 Correct 42 ms 57428 KB Output is correct
6 Correct 44 ms 57552 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55892 KB Output is correct
2 Correct 26 ms 55928 KB Output is correct
3 Correct 26 ms 55868 KB Output is correct
4 Correct 28 ms 55896 KB Output is correct
5 Correct 29 ms 55888 KB Output is correct
6 Correct 27 ms 55892 KB Output is correct
7 Correct 26 ms 55892 KB Output is correct
8 Correct 103 ms 100752 KB Output is correct
9 Correct 139 ms 98788 KB Output is correct
10 Runtime error 152 ms 196560 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -