Immediate Decodability

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int son[N][2], cnt[N], idx;
char str[N];
int casei;
bool flag;

bool insert(char str[]) {
    int p = 0;

    for (int i = 0; str[i]; i ++ ) {

        int u = str[i] - '0';

        if (!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];

        if (cnt[p])
            return true;
    }

    for (int i = 0; i < 2; i ++ )

        if (son[p][i])
            return true;
    cnt[p] ++ ;
    return false;
}

int main() {
    while (~scanf("%s", str)) {
        if (str[0] == '9') {
            if (!flag)
                printf("Set %d is immediately decodable\n", ++ casei);
            else
                printf("Set %d is not immediately decodable\n", ++ casei);
            memset(son, 0, sizeof son);
            memset(cnt, 0, sizeof cnt);
            idx = 0;
            flag = false;
        } else if (insert(str))
            flag = true;
    }

    return 0;
}

Xor Sum

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 33 * N;

typedef long long LL;

LL a[N];
LL son[M][2], idx;
int n, m;
int casei;

void insert(LL x) {
    int p = 0;

    for (int i = 32; i >= 0; i -- ) {

        int u = x >> i & 1;

        if (!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];
    }
}

LL query(LL x) {
    int p = 0;
    LL res = 0;

    for (int i = 32; i >= 0; i -- ) {

        int u = x >> i & 1;

        if (son[p][!u]) {
            p = son[p][!u];
            res = res * 2 + !u;
        } else {
            p = son[p][u];
            res = res * 2 + u;
        }
    }

    return res;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        memset(son, 0, sizeof son);
        idx = 0;
        scanf("%d%d", &n, &m);

        for (int i = 0; i < n; i ++ ) {

            scanf("%lld", &a[i]);
            insert(a[i]);
        }

        printf("Case #%d:\n", ++ casei);

        while (m -- ) {
            LL b;
            scanf("%lld", &b);
            printf("%lld\n", query(b));
        }
    }

    return 0;
}

Shortest Prefixes

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 20 * N;

char a[N][30];
int pos = -1;
int son[M][26], idx;
int cnt[M];

void insert(int j) {
    int p = 0;

    for (int i = 0; a[j][i]; i ++ ) {

        int u = a[j][i] - 'a';

        if (!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] ++ ;
    }
}

void query(int j) {
    int p = 0;

    for (int i = 0; a[j][i]; i ++ ) {

        int u = a[j][i] - 'a';
        putchar(a[j][i]);
        p = son[p][u];

        if (cnt[p] == 1)
            break;
    }

    putchar('\n');
}

int main() {
    while (~scanf("%s", a[ ++ pos])) {
        insert(pos);
    }

    for (int i = 0; i <= pos; i ++ ) {

        printf("%s ", a[i]);
        query(i);
    }

    return 0;
}

Babelfish

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

const int N = 20, M = 1e6 + 10;

char s[40], a[N], b[N];
int son[M][26], idx;
map<string, string> mp;

void insert(char str[]) {
    int p = 0;

    for (int i = 0; str[i]; i ++ ) {

        int u = str[i] - 'a';

        if (!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];
    }
}

bool query(char str[]) {
    int p = 0;

    for (int i = 0; str[i]; i ++ ) {

        int u = str[i] - 'a';

        if (!son[p][u])
            return false;
        p = son[p][u];
    }

    return true;
}

int main() {
    while (gets(s)) {
        if (s[0] == '\0')
            break;
        sscanf(s, "%s %s", a, b);
        mp[b] = a;
        insert(b);
    }

    while (gets(a)) {
        if (query(a))
            cout << mp[a] << endl;
        else
            puts("eh");
    }

    return 0;
}