Submission #1138948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138948		SSKMF	Klasika (COCI20_klasika)	C++20	110 / 110	4159 ms	35896 KiB

klasika

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

const int lungime_bloc = 600;
pair <int , int> arbore[6000000];
struct Operatie { int8_t tip; pair <int , int> valoare; } operatii[200001];
int cantitate , urmatorul[200002] , capat[200002] , inceput[200002] , sfarsit[200002] , valoare[200002];

inline void Parcurgere (const int nod_actual)
{
    inceput[nod_actual] = ++inceput[0];
    for (int indice = capat[nod_actual] ; indice ; indice = urmatorul[indice])
        { Parcurgere(indice); }

    sfarsit[nod_actual] = inceput[0];
}

inline void Insert (int& nod , const int valoare , const int putere)
{
    if (!nod)
        { nod = ++cantitate; }

    if (!putere)
        { return; }

    if (valoare & putere)
        { Insert(arbore[nod].second , valoare , putere >> 1); }
    else
        { Insert(arbore[nod].first , valoare , putere >> 1); }
}

inline int Query (const int nod , const int valoare , const int putere)
{
    if (!putere)
        { return 0; }

    if (valoare & putere) {
        if (arbore[nod].first)
            { return Query(arbore[nod].first , valoare , putere >> 1) | putere; }
        return Query(arbore[nod].second , valoare , putere >> 1);
    }

    if (arbore[nod].second)
        { return Query(arbore[nod].second , valoare , putere >> 1) | putere; }
    return Query(arbore[nod].first , valoare , putere >> 1);
}

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

    int numar_operatii;
    cin >> numar_operatii;

    int lungime = 1;
    for (int indice = 1 ; indice <= numar_operatii ; indice++)
    {
        char tip[8];
        cin >> tip >> operatii[indice].valoare.first >> operatii[indice].valoare.second;
        operatii[indice].tip = tip[0];
        
        if (operatii[indice].tip == 'A') 
        { 
            urmatorul[++lungime] = capat[operatii[indice].valoare.first]; 
            capat[operatii[indice].valoare.first] = lungime;
        }
    }

    Parcurgere(1);

    for (int indice = 2 ; indice <= lungime ; indice++)
        { valoare[indice] = -1; }

    cantitate = lungime / lungime_bloc + 1; lungime = 1;
    for (int indice = 1 ; indice <= numar_operatii ; indice++) {
        if (operatii[indice].tip == 'A')
        {
            lungime++;
            const int actual = (valoare[inceput[operatii[indice].valoare.first]] ^ operatii[indice].valoare.second);
            int temporar = inceput[lungime] / lungime_bloc + 1;
            Insert(temporar , actual , (1 << 30));
            valoare[inceput[lungime]] = actual;
        }
        else
        {
            int maxim = 0;
            int stanga = inceput[operatii[indice].valoare.second];
            int dreapta = sfarsit[operatii[indice].valoare.second];
            const int termen = valoare[inceput[operatii[indice].valoare.first]];
            const int bloc_1 = inceput[operatii[indice].valoare.second] / lungime_bloc + 1;
            const int bloc_2 = sfarsit[operatii[indice].valoare.second] / lungime_bloc + 1;
            if (bloc_1 == bloc_2) {
                for ( ; stanga <= dreapta ; stanga++) {
                    if (valoare[stanga] != -1)
                        { maxim = max(maxim , valoare[stanga] ^ termen); }
                }
            } else {
                for (int indice = bloc_1 * lungime_bloc - 1 ; indice >= stanga ; indice--) {
                    if (valoare[indice] != -1)
                        { maxim = max(maxim , valoare[indice] ^ termen); }
                }
                for (int indice = (bloc_2 - 1) * lungime_bloc ; indice <= dreapta ; indice++) {
                    if (valoare[indice] != -1)
                        { maxim = max(maxim , valoare[indice] ^ termen); }
                }
                for (int indice = bloc_1 + 1 ; indice < bloc_2 ; indice++)
                    { maxim = max(maxim , Query(indice , termen , (1 << 30))); }
            }

            cout << maxim << '\n';
        }
    }

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44