oj.uz

Submission #1079192

# Submission time Handle Problem Language Result Execution time Memory
1079192 2024-08-28T11:50:43 Z Andrey Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1346 ms 962924 KB 
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> trie[2000001];
vector<int> sb[2000001];
vector<int> yo[2000001];
vector<int> idk[2000001];
vector<int> lol[2000001];
vector<string> haha(2000001);
vector<pair<string,string>> query(2000001);
vector<int> ans(2000001);

int wow(char a) {
    if(a == 'A') {
        return 0;
    }
    if(a == 'G') {
        return 1;
    }
    if(a == 'C') {
        return 2;
    }
    if(a == 'U') {
        return 3;
    }
}

void ins(int p, int x, string& s, int d, int br, bool no) {
    if(d >= s.size()) {
        if(br != -1) {
            if(no) {
                yo[x].push_back(br);
            }
            else {
                idk[x].push_back(br);
            }
        }
        sb[p][x]++;
        return;
    }
    int c = wow(s[d]);
    if(trie[p][x][c] == -1) {
        if(!no) {
            return;
        }
        trie[p][x][c] = trie[p].size();
        trie[p].push_back({-1,-1,-1,-1});
        sb[p].push_back(0);
    }
    sb[p][x]-=sb[p][trie[p][x][c]];
    ins(p,trie[p][x][c],s,d+1,br,no);
    sb[p][x]+=sb[p][trie[p][x][c]];
}

int calc(int p, int x, int d, string& s) {
    if(x == -1) {
        return 0;
    }
    if(d == s.size()) {
        return sb[p][x];
    }
    int c = wow(s[d]);
    return calc(p,trie[p][x][c],d+1,s);
}

void dfs(int x, int d) {
    vector<pair<int,int>> wut(0);
    for(int i = 0; i < 4; i++) {
        if(trie[0][x][i] != -1) {
            dfs(trie[0][x][i],d+1);
            wut.push_back({trie[trie[0][x][i]].size(),trie[0][x][i]});
        }
    }
    sort(wut.begin(),wut.end());
    reverse(wut.begin(),wut.end());
    if(wut.size() > 0) {
        swap(trie[x],trie[wut[0].second]);
        swap(lol[x],lol[wut[0].second]);
        swap(sb[x],sb[wut[0].second]);
        for(int i = 1; i < wut.size(); i++) {
            for(int v: lol[wut[i].second]) {
                reverse(haha[v].begin(),haha[v].end());
                ins(x,0,haha[v],0,-1,1);
                reverse(haha[v].begin(),haha[v].end());
                lol[x].push_back(v);
            }
        }
        for(int i = 0; i < wut.size(); i++) {
            trie[wut[i].second].clear();
            lol[wut[i].second].clear();
            sb[wut[i].second].clear();
        }
    }
    for(int i = 0; i < yo[x].size(); i++) {
        int v = yo[x][i];
        reverse(haha[v].begin(),haha[v].end());
        ins(x,0,haha[v],0,-1,1);
        reverse(haha[v].begin(),haha[v].end());
        lol[x].push_back(yo[x][i]);
    }
    for(int v: idk[x]) {
        ans[v] = calc(x,0,0,query[v].second);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q;
    cin >> n >> q;
    string s,a,b;
    for(int i = 0; i <= 2000000; i++) {
        trie[i].push_back({-1,-1,-1,-1});
        sb[i].push_back(0);
    }
    trie[0].push_back({-1,-1,-1,-1});
    sb[0].push_back(0);
    for(int i = 0; i < n; i++) {
        cin >> s;
        haha[i] = s;
        ins(0,1,s,0,i,1);
    }
    for(int i = 0; i < q; i++) {
        cin >> a >> b;
        reverse(b.begin(),b.end());
        query[i] = {a,b};
        ins(0,1,a,0,i,0);
    }
    dfs(1,0);
    for(int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'void ins(int, int, std::string&, int, int, bool)':
selling_rna.cpp:29:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if(d >= s.size()) {
      |        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int calc(int, int, int, std::string&)':
selling_rna.cpp:59:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if(d == s.size()) {
      |        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'void dfs(int, int)':
selling_rna.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i = 1; i < wut.size(); i++) {
      |                        ~~^~~~~~~~~~~~
selling_rna.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i = 0; i < wut.size(); i++) {
      |                        ~~^~~~~~~~~~~~
selling_rna.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i < yo[x].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'int wow(char)':
selling_rna.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 618832 KB Output is correct
2 Correct 445 ms 618836 KB Output is correct
3 Correct 462 ms 618844 KB Output is correct
4 Correct 384 ms 618836 KB Output is correct
5 Correct 384 ms 618832 KB Output is correct
6 Correct 376 ms 618836 KB Output is correct
7 Correct 380 ms 618840 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 798364 KB Output is correct
2 Correct 776 ms 797684 KB Output is correct
3 Correct 993 ms 806036 KB Output is correct
4 Correct 1035 ms 799576 KB Output is correct
5 Correct 1285 ms 959248 KB Output is correct
6 Correct 1346 ms 962924 KB Output is correct
7 Correct 486 ms 630612 KB Output is correct
8 Correct 926 ms 811812 KB Output is correct
9 Correct 841 ms 774716 KB Output is correct
10 Correct 897 ms 805832 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 620240 KB Output is correct
2 Correct 448 ms 620840 KB Output is correct
3 Correct 449 ms 620628 KB Output is correct
4 Correct 400 ms 620088 KB Output is correct
5 Correct 464 ms 620884 KB Output is correct
6 Correct 459 ms 621000 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 618832 KB Output is correct
2 Correct 445 ms 618836 KB Output is correct
3 Correct 462 ms 618844 KB Output is correct
4 Correct 384 ms 618836 KB Output is correct
5 Correct 384 ms 618832 KB Output is correct
6 Correct 376 ms 618836 KB Output is correct
7 Correct 380 ms 618840 KB Output is correct
8 Correct 748 ms 798364 KB Output is correct
9 Correct 776 ms 797684 KB Output is correct
10 Correct 993 ms 806036 KB Output is correct
11 Correct 1035 ms 799576 KB Output is correct
12 Correct 1285 ms 959248 KB Output is correct
13 Correct 1346 ms 962924 KB Output is correct
14 Correct 486 ms 630612 KB Output is correct
15 Correct 926 ms 811812 KB Output is correct
16 Correct 841 ms 774716 KB Output is correct
17 Correct 897 ms 805832 KB Output is correct
18 Correct 389 ms 620240 KB Output is correct
19 Correct 448 ms 620840 KB Output is correct
20 Correct 449 ms 620628 KB Output is correct
21 Correct 400 ms 620088 KB Output is correct
22 Correct 464 ms 620884 KB Output is correct
23 Correct 459 ms 621000 KB Output is correct
24 Correct 774 ms 786612 KB Output is correct
25 Correct 772 ms 787352 KB Output is correct
26 Correct 796 ms 784568 KB Output is correct
27 Correct 1016 ms 781772 KB Output is correct
28 Correct 651 ms 660784 KB Output is correct
29 Correct 510 ms 624840 KB Output is correct