Submission #1069806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069806		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	535 ms	149696 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front

int const maxn = 5e6 + 7;
const ll INF = LLONG_MAX;

char Change(char c)
{
    if(c == 'C') return 'A';
    if(c == 'U') return 'B';
    if(c == 'G') return 'C';
    if(c == 'A') return 'D';
}

struct Trie
{
    struct Node
    {
        int child[4][4];
        int exist , cnt;
    } node[maxn];

    int cur;

    Trie() : cur(0)
    {
        memset(node[0].child , -1 , sizeof(node[0].child));
        node[0].exist = node[0].cnt = 0;
    }

    int Make_Note()
    {
        cur ++;
        memset(node[cur].child , -1 , sizeof(node[cur].child));
        node[cur].exist = node[cur].cnt = 0;

        return cur;
    }

    void Add_String(string s)
    {
        int pos = 0;
        int le = s.size();
        //cout << "le " << le << "\n";
        for(int i = 0 ; i < le ; i ++){
                int c1 = Change(s[i]) - 'A';
                int c2 = Change(s[le - 1 - i]) - 'A';
                //cout << "? " << c1 << " " << c2 << "\n";
                if(node[pos].child[c1][c2] == -1){
                        node[pos].child[c1][c2] = Make_Note();
                }
                pos = node[pos].child[c1][c2];
                node[pos].cnt ++;
        }
        node[pos].exist ++;
       // cout << "cur " << cur << "\n";
    }

    void Count_On(int& s , int pos , string s1 , int l , int r , int op)
    {
        //cout << "l r " << l << " " << r << "\n";
        if(op == 0){
                if(l == r){
                        int c = Change(s1[l]) - 'A';
                        for(int i = 0 ; i <= 3 ; i ++){
                                if(node[pos].child[c][i] != -1){
                                        s += node[node[pos].child[c][i]].cnt;
                                }
                        }
                        return;
                }

                int c = Change(s1[l]) - 'A';
                for(int i = 0 ; i <= 3 ; i ++){
                        if(node[pos].child[c][i] != -1){
                                pos = node[pos].child[c][i];
                                Count_On(s , pos , s1 , l + 1 , r , op);
                        }
                }
        }

        else{
                if(l == r){
                        int c = Change(s1[l]) - 'A';
                        for(int i = 0 ; i <= 3 ; i ++){
                                if(node[pos].child[i][c] != -1){
                                        s += node[node[pos].child[i][c]].cnt;
                                }
                        }
                        return;
                }

                int c = Change(s1[l]) - 'A';
                for(int i = 0 ; i <= 3 ; i ++){
                        if(node[pos].child[i][c] != -1){
                                pos = node[pos].child[i][c];
                                Count_On(s , pos , s1 , l + 1 , r , op);
                        }
                }
        }

    }

    int Find_String(string s1 , string s2)
    {
        int pos = 0;
        int le1 = s1.size();
        int le2 = s2.size();
        int op;
        le1 > le2 ? op = 0 : op = 1;
        for(int i = 0 ; i < min(le1 , le2)  ; i ++){
                int c1 = Change(s1[i]) - 'A';
                int c2 = Change(s2[i]) - 'A';
                if(node[pos].child[c1][c2] == -1) return 0;
                pos = node[pos].child[c1][c2];
        }

        //cout << "pos " << pos << "\n";
        int re = 0;
        if(le1 != le2){
                if(op == 0) Count_On(re , pos , s1 , le2 , le1 - 1 , op);
                else Count_On(re , pos , s2 , le1 , le2 - 1 , op);
        }
        else{
                re += node[pos].cnt;
        }

        //if(!node[pos].exist) return 0;
        return re;
    }
};

Trie trie;
int n , q;
string s , s1 , s2;

void Input()
{
    cin >> n >> q;
    for(int i = 1 ; i <= n ; i ++){
            cin >> s;
            trie.Add_String(s);
    }
}

void Solve()
{
    for(int i = 1 ; i <= q ; i ++){
            cin >> s1 >> s2;
            reverse(s2.begin() , s2.end());
            cout << trie.Find_String(s1 , s2) << "\n";
    }

}

int main()
{
    ios_base::sync_with_stdio(false);  cin.tie(nullptr);
   // freopen(".INP","r",stdin);
   // freopen(".OUT","w",stdout);
    int tt = 1;
    //cin >> tt;
    while(tt--){
            Input();
            Solve();
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'char Change(char)':
selling_rna.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
   20 | }
      | ^

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