Solução Informática Avançado - Semana 48

Solução por Sofhia Souza

O problema se resume basicamente ao algoritmo de Union Find, onde as ações de juntar os jogadores se referem à função join do algoritmo (caso não conheça, recomendamos que estude sobre o algoritmo antes de resolver o problema). A única diferença da resolução desse problema para o algoritmo original, é que a cada união que fizermos, somaremos o valor dos pontos da guilda do jogador B na guilda do jogador A (pois sempre igualaremos B à A, e não o contrário). Nas ações de batalhas, eu verifico se Rafael está em alguma das guildas e se sim, comparo os pontos das duas guildas e somo uma vitória ao meu contador (caso a guilda de Rafael tenha sido vencedora).
Segue o código para melhor entendimento:


#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n, m, pontos[MAXN], comp[MAXN];
inline int find(int x)
{
if(comp[x] == x) return x;
return comp[x] = find(comp[x]);
}
inline void join(int a, int b)
{
comp[find(a)] = find(b);
}
int main()
{
cin >> n >> m;
for(int i = 0 ; i < n ; i++)
{
cin >> pontos[i];
comp[i] = i;
}
int cont = 0;
for(int i = 0 ; i < m ; i++)
{
int q, a, b;
cin >> q >> a >> b;
if(q == 1)
{
pontos[find(b)] += pontos[find(a)];
join(a, b);
}
else
{
if(find(1) == find(a) and pontos[find(a)] > pontos[find(b)]) cont++;
else if(comp[1] == comp[b] and pontos[comp[b]] > pontos[comp[a]]) cont++;
}
}
cout << cont << endl;
}