Comentário Problema Startup

Startup

Comentário escrito por João Pedro Castro

Podemos visualizar a hierarquia dessa empresa como um grafo, onde os vértices (funcionários) tem outros vértices se ligando à ele (os subordinados). Além da estrutura do grafo, para cada funcionário vamos guardar seu chefe, salário, e a quantidade de subordinados com os quais ele está insatisfeito. Também é necessário guardar a quantidade de funcionários insatisfeitos no total, chamaremos esse valor de $f$ .

Após montar o grafo (feito com as arestas sendo: $\text{chefe} \rightarrow \text{subordinado}$ ), receber o chefe de cada um e o salário, para preencher a quantidade de insatisfações basta percorrer o grafo começando do vértice 1 e aumentando o valor de $insatisfacoes[vertice]$ em uma unidade toda vez que $f$ em 1 caso $insatisfacoes[vertice] = 0$ , já que o estado do $vertice$ vai mudar de satisfeito para insatisfeito.

Para todo funcionário $i$ atualizado a ideia é checar se o “estado” (satisfeito ou insatisfeito) de seu chefe e dele mesmo (em relação ao seus subordinados) foram alterados, já que eles são os únicos com os quais isso pode ter acontecido. E isso pode ser feito com uma série de estruturas condicionais, que se resumem à:

(chefe insatisfeito antes com o funcionário) e (chefe satisfeito agora)
(chefe satisfeito antes com o funcionário) e (chefe insatisfeito agora)

Agora, para achar o valor de $f$ (a resposta) atualizado, é só seguir o seguinte algoritimo:

Se $insatisfacoes[chefe[i]]++$
Se $insatisfacoes[chefe[i]] = 1$ (novo chefe insatisfeito):
- $f++$

Se não se:

$insatisfacoes[chefe[i]]--$

$insatisfacoes[chefe[i]] = 0$ (chefe satisfeito de novo):

$f--$

Para cada subordinado

$u$ de

$i$ :

Se $insatisfacoes[i]++$
Se $insatisfacoes[i] = 1$ (novo chefe insatisfeito):
- $f++$

Se não se:

$insatisfacoes[i]--$

$insatisfacoes[i] = 0$ (chefe satisfeito de novo):

$f--$

$salario[i] = novoSalario$

$imprimir~f$

Assim você também garante que os valores de $insatisfacoes$ e $f$ sempre permanecem atualizados. Segue a solução em C++:

	#include <bits/stdc++.h>

	using namespace std;

	vector<vector<int>> adj;
	vector<int> salario;
	vector<int> chefe;
	vector<int> insatisfacoes;

	int f;

	void dfs(int i) {
	for (auto u : adj[i]) {
	if (u == chefe[i]) continue;
	if (salario[u] > salario[i]) {
	if (insatisfacoes[i] == 0) f++;
	insatisfacoes[i]++;
	}
	dfs(u);
	}
	}

	int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, a;
	cin >> n;
	adj.resize(n+1);
	salario.resize(n+1);
	chefe.resize(n+1);
	insatisfacoes.resize(n+1);

	for (int i = 1; i <= n; i++) {
	cin >> chefe[i] >> salario[i];
	adj[chefe[i]].push_back(i);
	}

	dfs(1);
	cout << f << "\n";
	cin >> a;
	while (a–) {
	int i, novoSalario;
	cin >> i >> novoSalario;
	if (i != 1) {
	if ((salario[chefe[i]] >= salario[i]) and (novoSalario > salario[chefe[i]])) {
	insatisfacoes[chefe[i]]++;
	if (insatisfacoes[chefe[i]] == 1) f++;
	}
	else if ((salario[i] > salario[chefe[i]]) and (salario[chefe[i]] >= novoSalario)) {
	insatisfacoes[chefe[i]]–;
	if (insatisfacoes[chefe[i]] == 0) f–;
	}
	}
	for (auto u : adj[i]) {
	if ((salario[i] >= salario[u]) and (salario[u] > novoSalario)) {
	insatisfacoes[i]++;
	if (insatisfacoes[i] == 1) f++;
	}
	else if ((salario[u] > salario[i]) and (novoSalario >= salario[u])) {
	insatisfacoes[i]–;
	if (insatisfacoes[i] == 0) f–;
	}
	}
	cout << f << "\n";
	salario[i] = novoSalario;
	}
	}

view raw

startup.cpp

hosted with ❤ by GitHub