Submission #1079183

# Submission time Handle Problem Language Result Execution time Memory
1079183 2024-08-28T11:46:22 Z Andrey Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
1004 ms 1048576 KB
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> trie[4000001];
vector<int> sb[4000001];
vector<int> yo[4000001];
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 < 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:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     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 | }
      | ^
# Verdict Execution time Memory Grader output
1 Correct 454 ms 759636 KB Output is correct
2 Correct 450 ms 759632 KB Output is correct
3 Correct 496 ms 759636 KB Output is correct
4 Correct 426 ms 759688 KB Output is correct
5 Correct 467 ms 759916 KB Output is correct
6 Correct 446 ms 759784 KB Output is correct
7 Correct 494 ms 759656 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 848 ms 992152 KB Output is correct
2 Correct 836 ms 993536 KB Output is correct
3 Correct 1000 ms 1004948 KB Output is correct
4 Correct 1004 ms 996504 KB Output is correct
5 Runtime error 714 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 436 ms 760732 KB Output is correct
2 Correct 480 ms 761684 KB Output is correct
3 Correct 517 ms 761424 KB Output is correct
4 Correct 460 ms 760560 KB Output is correct
5 Correct 538 ms 761680 KB Output is correct
6 Correct 537 ms 761548 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 454 ms 759636 KB Output is correct
2 Correct 450 ms 759632 KB Output is correct
3 Correct 496 ms 759636 KB Output is correct
4 Correct 426 ms 759688 KB Output is correct
5 Correct 467 ms 759916 KB Output is correct
6 Correct 446 ms 759784 KB Output is correct
7 Correct 494 ms 759656 KB Output is correct
8 Correct 848 ms 992152 KB Output is correct
9 Correct 836 ms 993536 KB Output is correct
10 Correct 1000 ms 1004948 KB Output is correct
11 Correct 1004 ms 996504 KB Output is correct
12 Runtime error 714 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -