1285D - Dr Evil Underscores - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a, trie[10000005][2], k = 1, ans = 0, cnt;
ll b[50], poww[50];
void insertt(ll x)
{
    memset(b, 0, sizeof(b));
    cnt = 0;
    while (x)
    {
        b[cnt] = x % 2;
        x = x / 2;
        cnt++;
    }
    ll p = 0;
    for (ll i = 29; i >= 0; i--)
    {
        if (trie[p][b[i]] == 0)
        {
            trie[p][b[i]] = k;
            k++;
        }
        p = trie[p][b[i]];
    }
}
ll dfs(ll now, ll deep)
{
    if (trie[now][1] == 0 && trie[now][0] == 0)
        return 0; //该节点已经没有子节点
    if (trie[now][1] == 0)
        return dfs(trie[now][0], deep - 1); //该节点只有0子节点
    if (trie[now][0] == 0)
        return dfs(trie[now][1], deep - 1); //该节点只有1子节点
    //只有0子节点或只有1子节点，则在异或完以后最大的数中 这一位是0，所以不需要加上poww[deep]
    return poww[deep] + min(dfs(trie[now][0], deep - 1), dfs(trie[now][1], deep - 1));
    //该节点同时有1和0子节点，则在异或完以后最后最大数中 这一位一定为1，所以需要加上的poww[deep]
}
int main()
{
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
    {
        scanf("%lld", &a);
        insertt(a);
    }
    poww[0] = 1;
    for (ll i = 1; i <= 29; i++)
        poww[i] = poww[i - 1] * 2;
    printf("%lld\n", dfs((ll)0, (ll)29));
}