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 $$salario[subordinado] > salario[vertice]$$, quando isso acontecer, também aumente $$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 $$i \neq 1 ~\&~ salario[i] \geq salario[chefe[i]] ~\&~ novoSalario > salario[chefe[i]]$$
- $$insatisfacoes[chefe[i]]++$$
- Se $$insatisfacoes[chefe[i]] = 1$$ (novo chefe insatisfeito):
- $$f++$$
- Se não se: $$salario[i] > salario[chefe[i]] ~\&~ salario[chefe[i]] \geq novoSalario$$
- $$insatisfacoes[chefe[i]]–$$
- Se $$insatisfacoes[chefe[i]] = 0$$ (chefe satisfeito de novo):
- $$f–$$
- Para cada subordinado $$u$$ de $$i$$:
- Se $$salario[i] \geq salario[u] ~\&~ salario[u] > novoSalario$$:
- $$insatisfacoes[i]++$$
- Se $$insatisfacoes[i] = 1$$ (novo chefe insatisfeito):
- $$f++$$
- Se não se: $$salario[u] > salario[i] ~\&~ novoSalario \geq salario[u]$$:
- $$insatisfacoes[i]–$$
- Se $$insatisfacoes[i] = 0$$ (chefe satisfeito de novo):
- $$f–$$
- Se $$salario[i] \geq salario[u] ~\&~ salario[u] > novoSalario$$:
- $$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++:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } | |
| } |