URI PROBLEMA 1269 - ICPC Ataca Novamente SOLUÇÃO EM C++

URI Online Judge | 1269

ICPC Ataca Novamente

Por Alessandro Luna Almeida  Brasil

Timelimit: 3

A Companhia Internacional de Projetos Concretos (ICPC) é uma empresa de construção especializada na construção de casas para o mercado high-end. A empresa é mais rentável do mundo devido a um método muito eficiente em divisão de terras que tem sido usado em seus projetos de desenvolvimento de habitações desde o ano passado. Recentemente houve um caos na ICPC, porque os funcionários se recusaram a trabalhar alegando que eles não ganhavam o suficiente. Preocupado com a perda de lucros devido à greve, a diretoria da empresa propôs um novo método para calcular os salários, que foi felizmente aceito por todos.

O salário de um trabalhador reflete na importância das tarefas que ele / ela tem para realizar e é influenciado pela forma como as tarefas dependem uma das outras.

Uma tarefa X depende de uma tarefa Y se (i) X depende diretamente de Y, ou (ii) existe uma tarefa T tal que X depende diretamente de T e T depende de Y. Uma vez que todas as tarefas em ICPC devem ser realizadas, não há circularidade da relação de dependência da tarefa. Além disso, a tarefa pode ser realizada por mais do que um trabalhador. Um significado básico está associado com cada tarefa que reflete na sua importância (por exemplo, o desenvolvimento de um método eficiente na divisão de terras é mais importante do que a construção de casas em si). O significado de uma tarefa T é então definido como o significado básico de T mais o significado de cada tarefa que depende diretamente de T.

Note que se nenhuma outra tarefa depende diretamente da tarefa T, o significado básico e o significado de T são iguais.

O salário de um trabalhador é a soma dos significados de todas as tarefas que ele executa as quais não dependem de qualquer outra tarefa realizada por ele. Em outras palavras, um valor igual ao significado da tarefa X será adicionado ao salário de um trabalhador W que trabalha em uma tarefa X se não houver nenhuma outra tarefa Y da qual X depende, e na qual W trabalha também em Y.

ICPC deseja que você ajude-os a determinar o salário de cada um de seus funcionários.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois inteiros T e E indicando, respectivamente, o número de tarefas e do número de empregados (1 ≤ T ≤ 1000 e 1 ≤ E ≤ 1000). As tarefas são numeradas de 1 a T e empregados de 1 a E.

Em seguida, vai vir uma sequência de linhas que descrevem as tarefas 1 a T em ordem crescente. Cada tarefa é descrita por duas linhas. A primeira dessas linhas contém três inteiros BS, ND e NE, representando respectivamente o significado básico da tarefa, o número de tarefas que dependem diretamente sobre ela, e o número de empregados que executam-la (1 ≤ BS ≤ 1000, 0 ≤ ND < T e 1 ≤  NE ≤ E). A segunda linha contém inteiros ND + NE correspondentes primeiro ao ND que tem tarefas diretamente dependentes e depois os funcionários NE que executaram a tarefa. O fim da entrada é indicado por T = E = 0.

Saída

Os casos de teste devem ser respondidos na ordem em que foram apresentados. Para cada caso de teste, você deve imprimir:
• uma única linha contendo cinco estrelas ***** indicando o início do processo
• para cada empregado i, uma linha com dois inteiros i e s, separados por um espaço em branco, o que significa que i tem um salário de s.

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#define MAXN 1001

using namespace std;

vector<int> grafo[MAXN],novo_grafo[MAXN],tarefas[MAXN],novas_tarefas[MAXN];

int grau[MAXN],processado[MAXN],marcado[MAXN],valor[MAXN],novo_valor[MAXN],dp[MAXN],conversao[MAXN],reverso[MAXN],n,m,contador;

int dfs1(int x){

if(dp[x] != -1) return dp[x];

dp[x] = novo_valor[x];

for(int i=0;i<novo_grafo[x].size();i++){

int v = novo_grafo[x][i];

dp[x] += dfs1(v);

}

return dp[x];

}

void dfs2(int x){

processado[x] = 1;

for(int i=0;i<novo_grafo[x].size();i++){

int v = novo_grafo[x][i];

if(!processado[v]){

marcado[v] = 1;

dfs2(v);

}

}

}

int main(){

while(scanf("%d %d",&n,&m) && (n||m)){

//printf("%d %d\n",n,m);

for(int i=1;i<=max(n,m);i++){

grafo[i].clear();

novo_grafo[i].clear();

tarefas[i].clear();

novas_tarefas[i].clear();

processado[i] = 0;

marcado[i] = 0;

valor[i] = 0;

novo_valor[i] = 0;

grau[i] = 0;

conversao[i] = 0;

reverso[i] = 0;

dp[i] = -1;

}

contador = 0;

for(int i=1;i<=n;i++){

int qtd1,qtd2;

scanf("%d %d %d",&valor[i],&qtd1,&qtd2);

//printf("%d %d %d\n",valor[i],qtd1,qtd2);

while(qtd1--){

int davez;

scanf("%d",&davez);

//printf("%d %d\n",i,davez);

grafo[i].push_back(davez);

grau[davez]++;

}

while(qtd2--){

int davez;

scanf("%d",&davez);

//printf("%d %d\n",i,davez);

tarefas[davez].push_back(i);

}

}

queue<int> bfs;

for(int i=1;i<=n;i++){

if(grau[i] == 0) bfs.push(i);

}

while(!bfs.empty()){

int v = bfs.front();

bfs.pop();

conversao[v] = ++contador;

reverso[contador] = v;

for(int i=0;i<grafo[v].size();i++){

int u = grafo[v][i];

grau[u]--;

if(!grau[u]) bfs.push(u);

} 

}

for(int i=1;i<=n;i++){

int antigo = reverso[i];

novo_grafo[i] = grafo[antigo];

for(int j=0;j<novo_grafo[i].size();j++){

novo_grafo[i][j] = conversao[novo_grafo[i][j]];

}

sort(novo_grafo[i].begin(),novo_grafo[i].end());

novo_valor[i] = valor[antigo];

}

for(int i=1;i<=n;i++) dfs1(i);

printf("*****\n");

for(int i=1;i<=m;i++){

novas_tarefas[i] = tarefas[i];

for(int j=0;j<novas_tarefas[i].size();j++){

novas_tarefas[i][j] = conversao[novas_tarefas[i][j]];

}

sort(novas_tarefas[i].begin(),novas_tarefas[i].end());

int resp = 0;

memset(processado,0,sizeof(processado));

memset(marcado,0,sizeof(marcado));

for(int j=0;j<novas_tarefas[i].size();j++){

int v = novas_tarefas[i][j];

if(!processado[v]) dfs2(v);

}

for(int j=0;j<novas_tarefas[i].size();j++){

int v = novas_tarefas[i][j];

resp += (1 - marcado[v])*dfs1(v);

}

printf("%d %d\n",i,resp);

}

}

return 0;

}