SMMR-248: Battle Royale

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

unordered_map <string, vector <string>> member;
unordered_map <string, string> par;
unordered_map <string, int> val;
set <string> have;
const int INF = 2e9;
int n, Q;
bool found = false;
string mx;

void Ins(string str){
    if(have.find(str) != have.end()) return;
    val[str] = 0;
    par[str] = str;
    member[str].push_back(str);
    have.insert(str);
}

void Merge(string u, string v, int x){ /// u <- v
    par[v] = u;
    for(auto i: member[v]){
        member[u].push_back(i);
        par[i] = u;
        val[i] += x;
    }
    member[v].clear();
    if(member[u].size() == n) {
        mx = u;
        found = true;
    }
}

void Combine(string a, string b, int x){
    Ins(a);
    Ins(b);
    if(par[a] == par[b]) return;
    /// a >= b
    if(x < 0) swap(a, b);
    x = abs(x);
    if(val[b] > val[a] + x)
        Merge(par[b], par[a], val[b] - val[a] - x);
    else
        Merge(par[a], par[b], val[a] + x - val[b]);
}

int Query(string a, string b){
    if(par[a] != par[b]
    or have.find(a) == have.end()
    or have.find(b) == have.end())
        return INF;
    return val[b] - val[a];
}

int main(){

    scanf("%d%d", &n, &Q);

    while(Q--){
        int opr, x;
        string a, b;
        scanf("%d", &opr);
        if(opr == 1){
            cin >> a >> b;
            scanf("%d", &x);
            Combine(a, b, x);
        }
        else if(opr == 2){
            cin >> a >> b;
            int q = Query(a, b);
            if(q != INF) printf("%d\n", q);
            else printf("cannot tell\n");
        }
        else if(opr == 3){
            if(found) cout << mx << '\n';
            else printf("cannot tell\n");
        }
    }

    return 0;
}

/*

8 16
1 1 2 20
1 3 4 5
1 4 1 -55
1 5 6 -30
1 5 7 10
2 2 6
2 2 3
2 6 7
3
1 6 7 40
1 7 1 -70
2 5 1
2 7 8
3
1 7 8 20
3

7 12
1 3 1 2
1 6 7 -1
1 4 7 -3
1 7 3 4
1 2 5 3
1 2 1 1
3

10 20
1 3 5 -2
1 7 5 2
1 2 3 -1
1 5 4 1
2 2 7
2 4 7
2 7 3
1 8 9 -1
1 10 9 1
1 6 8 -2
1 6 1 5
3
2 1 10
2 8 1
1 3 6 -3
3
2 4 10
2 7 8
2 6 9

*/