Cod sursa(job #2679311)

Utilizator WladDalwMvladutu cristian vlad WladDalwM Data 30 noiembrie 2020 11:37:08
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

struct Trie
{
    int cnt;
    int nr;
    Trie *fiu[2];
    Trie(){fiu[0] = fiu[1] = NULL; cnt = 0;nr = 0;}
};

Trie *trie;

void insert(Trie *trie , int b , int nr)
{
    if(b == -1)
        {trie->nr++;return;}
    bool x = nr&(1<<b);
    if(trie->fiu[x] == NULL)
        trie->fiu[x] = new Trie, trie->cnt++;
    insert(trie->fiu[x] , b - 1, nr);
}

bool erase(Trie *trie , int b , int nr)
{
    if(b == -1)
        trie->nr--;
    else
    {
        bool x = nr&(1<<b);
        if(trie->fiu[x] != NULL)
        {
            if(erase(trie->fiu[x] , b - 1 , nr))
                trie->fiu[x] = 0, trie->cnt--;
        }
    }
    if(trie->cnt == 0 && trie->nr == 0)
        return 1;
    return 0;
}

int search(Trie *trie, int b , int nr)
{
    if(b == -1)
        return 0;
    bool x = nr&(1<<b);
    if(trie->fiu[1-x] != NULL)
    return 1<<b | search(trie->fiu[1-x] , b - 1 , nr);
    return search(trie->fiu[x] , b - 1 , nr);
}




int main()
{
    int n;
    cin >> n;
    trie = new Trie;
    insert(trie , 29 , 0);
    for(int i = 1; i <= n; ++i)
    {
        char c;
        int a;
        cin >> c >> a;
        if(c == '+')
            insert(trie , 29 , a);
        if(c == '-')
            erase(trie , 29 , a);
        if(c == '?')
            cout << search(trie , 29 , a) << '\n';
    }
    return 0;

}