Submission #1175454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175454		InvMOD	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	483 ms	697340 KiB

selling_rna

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()

const int N = 2e6 + 5, M = 1e5 + 5, C = 6;

struct Trie{
    struct Node{
        Node* child[C]; int cnt;
        Node(): cnt(0) {
            for(int i = 0; i < C; i++){
                child[i] = nullptr;
            }
        }
    };
    typedef Node* pNode;

    pNode root;
    Trie(){
        root = new Node();
    }

    void addStr(const string &s){
        pNode cur = root;
        for(const char &i : s){
            int c = int(i - 'A');
            if(cur->child[c] == nullptr) cur->child[c] = new Node();
            cur = cur->child[c];
            cur->cnt = cur->cnt + 1;
        }
    }

    int countStr(const string& q){
        pNode cur = root;
        for(const char& i : q){
            int c = int(i - 'A');
            if(cur->child[c] == nullptr) return 0;
            cur = cur->child[c];
        }
        return cur->cnt;
    }
};

int root, cntNode, child[N][C], sum_size[N], answer[M];

vector<string> save[N]; vector<int> Q[N]; string suf[M]; Trie trie[N];

void add_element(string& s){
    int cur = root;
    for(const char &i : s){
        int c = int(i - 'A');
        if(!child[cur][c]) child[cur][c] = ++cntNode;
        cur = child[cur][c];
    }
    reverse(all(s));
    save[cur].push_back(s);
    trie[cur].addStr(s); sum_size[cur] += sz(s);
}

bool add_Query(int cntQ, const string& s){
    int cur = root;
    for(const char &i : s){
        int c = int(i - 'A');
        if(!child[cur][c]){
            return false;
        }
        cur = child[cur][c];
    }
    Q[cur].push_back(cntQ);
    return true;
}

void merge_trie(int x, int v){
    if(sum_size[x] < sum_size[v]){
        swap(sum_size[x], sum_size[v]);
        swap(save[x], save[v]);
        swap(trie[x], trie[v]);
    }

    sum_size[x] += sum_size[v];
    while(sz(save[v])){
        string i = save[v].back(); save[v].pop_back();
        save[x].push_back(i);
        trie[x].addStr(i);
    }
}

void process_query(int x){
    for(int i = 0; i < C; i++){
        if(child[x][i]){
            int v = child[x][i];

            process_query(v);
            merge_trie(x, v);
        }
    }

    for(int id : Q[x]){
        answer[id] = trie[x].countStr(suf[id]);
    }
}

char Conv(char x){
    if(x == 'A') return 'A';
    if(x == 'G') return 'B';
    if(x == 'C') return 'C';
    if(x == 'U') return 'D';
    return 'Z';
}

void solve()
{
    int n,q; cin >> n >> q;

    cntNode = root = 1;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        for(char& c : s) c = Conv(c);

        add_element(s);
    }

    for(int i = 0; i < q; i++){
        string pre; cin >> pre >> suf[i];

        for(char& c : pre) c = Conv(c);
        for(char& c : suf[i]) c = Conv(c);

        reverse(all(suf[i]));
        add_Query(i, pre);
    }

    process_query(root);
    for(int i = 0; i < q; i++){
        cout << answer[i] << "\n";
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40