SMMR-T248: Battle Royale

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

typedef long long lli;

const int N = 2e5;
const int PB = 1e9 + 7;

map<lli, int> nameToIdx;
char *name[N + 1];
int ds[N + 1], sz[N + 1], lessThan[N + 1], mx[N + 1];

lli strHash(char *str){
    lli hsh = 0;
    int len = strlen(str);
    for(int i = 0; i < len; ++i){
        hsh *= PB;
        hsh += str[i];
    }
    return hsh;
}

int currIdx = 1;
int addName(char *str){
    lli hsh = strHash(str);
    map<lli, int>::iterator itr = nameToIdx.find(hsh);
    if(itr == nameToIdx.end()){
        nameToIdx[hsh] = currIdx;
        name[currIdx] = new char[11];
        strcpy(name[currIdx], str);
        return currIdx++;
    }
    return itr -> second;
}

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    int p = dsFind(ds[u]);
    lessThan[u] += lessThan[ds[u]];
    return ds[u] = p;
}

int main(){

    int nRobot, Q;
    scanf("%d%d", &nRobot, &Q);
    // DSU Setup
    for(int i = 1; i <= nRobot; ++i){
        ds[i] = i;
        sz[i] = 1;
        lessThan[i] = 0;
        mx[i] = i;
    }
    int setCnt = nRobot;
    while(Q--){
        char *strA = new char[11];
        char *strB = new char[11];
        int cmd;
        scanf("%d", &cmd);
        if(cmd == 1){ // Union
            int stronger;
            scanf("%s %s%d", strA, strB, &stronger);
            int u = addName(strA);
            int v = addName(strB);
            int headU = dsFind(u);
            int headV = dsFind(v);
            if(headU != headV){
                if(sz[headU] < sz[headV]){
                    swap(headU, headV);
                    swap(u, v);
                    stronger *= -1;
                }
                ds[headV] = ds[headU];
                sz[headU] += sz[headV];
                lessThan[headV] = stronger + lessThan[u] - lessThan[v];
                --setCnt;
                dsFind(mx[headV]);
                if(lessThan[mx[headV]] < lessThan[mx[headU]]){
                    mx[headU] = mx[headV];
                }
            }
        } else if(cmd == 2){ // u > v
            scanf("%s %s", strA, strB);
            int u = addName(strA);
            int v = addName(strB);
            if(dsFind(u) == dsFind(v)){
                cout << lessThan[v] - lessThan[u] << '\n';
            } else {
                cout << "cannot tell\n";
            }
        } else if(cmd == 3){ // Max of All
            if(setCnt == 1){
                printf("%s\n", name[mx[dsFind(1)]]);
            } else {
                cout << "cannot tell\n";
            }
        }
    }

    return 0;
}