Submission #1131508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131508		SSKMF	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	59 ms	68268 KiB

selling_rna

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

int cantitate = 1 , radacina[100001];
struct Nod { int aparitii[2] = { } , urmatorul[4] = { }; } arbore_1[2000001];
struct __Nod { int aparitii = 0 , urmatorul[4] = { }; } arbore_2[2000001];
stack < pair <int , int> > stiva;
string sir;

inline void Insert (int &anterior , int &actual , const int indice)
{
    actual = ++cantitate;
    arbore_2[actual] = arbore_2[anterior];
    arbore_2[actual].aparitii++;

    if (indice == -1)
        { return; }

    Insert(arbore_2[anterior].urmatorul[((sir[indice] == 'A' || sir[indice] == 'U') ? (sir[indice] == 'A' ? 0 : 1) : (sir[indice] == 'G' ? 2 : 3))] , arbore_2[actual].urmatorul[((sir[indice] == 'A' || sir[indice] == 'U') ? (sir[indice] == 'A' ? 0 : 1) : (sir[indice] == 'G' ? 2 : 3))] , indice - 1);
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime , numar_intrebari;
    cin >> lungime >> numar_intrebari;

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        cin >> sir;

        int nod = 1;
        for (auto& valoare : sir)
        {
            arbore_1[nod].aparitii[0]++;
            const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
            if (!arbore_1[nod].urmatorul[__urmatorul])
                { arbore_1[nod].urmatorul[__urmatorul] = ++cantitate; }

            nod = arbore_1[nod].urmatorul[__urmatorul];
        }

        arbore_1[nod].aparitii[0]++;
        arbore_1[nod].aparitii[1]++;
    }

    stiva.push({1 , 0});
    sir.resize(100001);

    cantitate = 0;
{   int __indice = 0;
    while (!stiva.empty())
    {
        const int nod_actual = stiva.top().first;
        while (stiva.top().second < 4)
        {
            if (arbore_1[nod_actual].urmatorul[stiva.top().second])
            {
                sir[stiva.size() - 1] = ((stiva.top().second < 2 ? (stiva.top().second == 0 ? 'A' : 'U') : (stiva.top().second == 2 ? 'G' : 'C')));
                
                const int nod_vecin = arbore_1[nod_actual].urmatorul[stiva.top().second++];
                for (int indice = 1 ; indice <= arbore_1[nod_vecin].aparitii[1] ; indice++)
                    { __indice++; Insert(radacina[__indice - 1] , radacina[__indice] , (int)stiva.size() - 1); }

                stiva.push({nod_vecin , 0});
                break;
            }

            stiva.top().second++;
        }

        if (stiva.top().second == 4)
            { stiva.pop(); }
    }
}
    while (numar_intrebari--)
    {
        cin >> sir;

        int nod = 1 , anterior = 0;
        for (auto& valoare : sir)
        {
            anterior += arbore_1[nod].aparitii[1];
            const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
            for (int __indice = 0 ; __indice < __urmatorul ; __indice++)
                { anterior += arbore_1[arbore_1[nod].urmatorul[__indice]].aparitii[0]; }

            if (!(nod = arbore_1[nod].urmatorul[__urmatorul]))
                { break; }
        }
        
        cin >> sir;
        
        reverse(sir.begin() , sir.end());
        
        int nod_1 = radacina[anterior] , nod_2 = radacina[anterior + arbore_1[nod].aparitii[0]];
        for (auto &valoare : sir)
        {
            const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
            nod_1 = arbore_2[nod_1].urmatorul[__urmatorul];
            nod_2 = arbore_2[nod_2].urmatorul[__urmatorul];
        }
        
        cout << arbore_2[nod_2].aparitii - arbore_2[nod_1].aparitii << '\n';
    }

    return 0;
}

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