| Submeter | Todas submissőes | Melhores | Voltar |
ESCALO11 - Escalonamento ótimo |
O SBC (System for Batch Computing) é um sistema operacional voltado para a execução sequencial de tarefas. O operador do sistema cria tarefas e o sistema operacional é responsável por agendar a execução destas tarefas.
Cada tarefa pode depender da conclusão de algumas tarefas para poder começar. Se uma tarefa A depende de uma tarefa B, a tarefa B deve terminar antes que a tarefa A inicie sua execução.
Além disto, cada tarefa possui uma prioridade. É sempre mais vantajoso para o sistema começar executando uma tarefa de mais alta prioridade, depois continuar executando uma tarefa de mais alta prioridade dentre as que sobraram e assim por diante.
Neste problema, será dado um inteiro N, que irá representar o número de tarefas no sistema. As tarefas serão numeradas de 0 até N−1. Tarefas com índice menor possuem prioridade maior, de forma que a tarefa 0 é a tarefa de mais alta prioridade, a tarefa 1 é a tarefa com a segunda maior prioridade e assim por diante, até a tarefa N−1, que é a tarefa com a menor prioridade. Além disso, serão dadas M relações de dependência entre as tarefas.
Seu objetivo será decidir se é possível executar as tarefas em alguma ordem. Caso seja possível, você deverá produzir uma ordem de execução ótima para as tarefas, isto é, desempate as ordens possíveis pela prioridade da primeira tarefa. Se o empate ainda persistir, desempate pela prioridade da segunda tarefa, e assim por diante.
Entrada
A primeira linha da entrada contém inteiros N e M. As próximas M linhas descrevem, cada uma, uma dependência entre as tarefas da entrada. Cada uma dessas linhas irá conter dois inteiros A e B que indicam que a tarefa B depende da tarefa A, isto é, que a tarefa A deve terminar antes que a tarefa B inicie.
Saída
Se não for possível ordenar as tarefas de forma que as dependências sejam satisfeitas, imprima uma única linha contendo o caracter "*". Caso contrário, imprima N linhas contendo cada uma um número inteiro. O inteiro na i-ésima linha deve ser o índice da i-ésima tarefa a ser executada na ordem ótima de execução das tarefas.
Restrições
- 0 ≤ N ≤ 50000.
- 0 ≤ M ≤ 200000.
- 0 ≤ A, B < N.
Exemplos
Entrada 3 1 2 0 Saída 1 2 0 Entrada 2 2 0 1 1 0 Saída *
| Adicionado por: | Wanderley Guimarăes |
| Data: | 2012-03-10 |
| Tempo limite: | 0.100s-1s |
| Tamanho do fonte: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Linguagem permitida: | Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL |
| Origem: | OBI 2011 - fase 2 nível 2 |
hide comments
|
2020-06-11 04:07:40
Last edit: 2021-10-16 06:12:14 |
|
|
2016-04-16 01:25:10 Elsio [UFABC]
Outra coisa que pode deixar muita gente presa por muito tempo é o uso do <set> como fila. Sabemos que na ordenação topológica não é necessário ordenar a fila, mas o gabarito do spoj é único. Ele exige uma permutação específica. Pra quem tá aprendendo programação esse nível desnecessário de dificuldade (técnica e não teórica) é realmente broxante! |
|
|
2016-04-15 06:03:28 Elsio [UFABC]
Wanderley, afinal, o que deve ser avaliado aqui? o algoritmo ou a linguagem/lib usada? Em primeiro lugar: Ordenação topológica. Como você sabe, uma ordenação pode ter permutações topologicamente corretas. Algoritmos diferentes (e corretos) podem gerar sequências diferentes, mas o spoj só aceitaria aquela que foi gerada para o gabarito. O sistema não tem como avaliar isso de forma flexivel então muitos problemas pedem a soma de termos por ex. Em segundo lugar: eu já cansei de ver aqui no spoj essa coisa de um algoritmo passar com stdio e não passar com iostream. São horas perdidas com a certeza de que o algoritmo está correto mas o spoj não aceita! |
|
|
2014-08-09 01:07:43 João Baptista de Paula e Silva
O mais interessante é que a diferença de tempo entre o stdio e o iostream é o suficiente para dar TLE. |