Submission #1275247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275247		nanaseyuzuki	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	195 ms	211400 KiB

selling_rna

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 2e6 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5;
const int inf = 1e9, base = 311;

int n, m, child[mn][5], cnt = 0, st[mn], ft[mn];
string b[mn];

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

void add(string s, int i){
    int u = 0;
    for(auto d : s){
        int c = Megumi(d);
        if(!child[u][c]) child[u][c] = ++ cnt;
        u = child[u][c];
        if(!st[u]) st[u] = i;
        ft[u] = i;
    }
}

int go(string s){
    int u = 0;
    for(auto d : s){
        int c = Megumi(d);
        if(!child[u][c]) return 0;
        u = child[u][c];
    }
    return u;
}

vector <int> Reina[mn];
int Nanase = 0, child2[mn][5];

void add_rev(string s, int i){
    int u = 0;
    for(auto d : s){
        int c = Megumi(d);
        if(!child2[u][c]) child2[u][c] = ++ Nanase;
        u = child2[u][c];
        Reina[u].push_back(i);
    }
}

int go_rev(string s){
    int u = 0;
    for(auto d : s){
        int c = Megumi(d);
        if(!child2[u][c]) return 0;
        u = child2[u][c];
    }
    return u;
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> b[i];
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++){
        add(b[i], i);
        reverse(all(b[i]));
        add_rev(b[i], i);
    }
    for(int i = 1; i <= m; i++){
        string p, q; cin >> p >> q;
        reverse(all(q));
        int Maria = go(p);
        int Kousaka = go_rev(q);
        auto it1 = lower_bound(all(Reina[Kousaka]), st[Maria]);
        auto it2 = upper_bound(all(Reina[Kousaka]), ft[Maria]);
        cout << it2 - it1 << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen("RNA.INP", "r")){
        freopen("RNA.INP", "r", stdin);
        freopen("RNA.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}

Compilation message (stderr)

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

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