Imprimă pagina - 916 Trenuri

Titlul: 916 Trenuri
Scris de: Marius Stroe din Iunie 26, 2009, 22:05:09

Aici puteÅ£i discuta despre problema Trenuri (http://infoarena.ro/problema/trenuri).

Titlul: RÄƒspuns: Trenuri
Scris de: Paul-Dan Baltescu din Iunie 28, 2009, 15:01:04

Am crescut limita de timp la 3.3 s pentru ca era foarte stransa. In plus, am adaugat in enunt o restrictie care lipsea.

Titlul: RÄƒspuns: Trenuri
Scris de: Bogdan-Cristian Tataroiu din Iunie 28, 2009, 23:14:30

Cred ca ar trebui adaugate id-urile problemelor in numele topicurilor la fel ca pentru celelalte probleme.

Titlul: RÄƒspuns: Trenuri
Scris de: Marius Stroe din Iunie 29, 2009, 10:58:02

Citat din mesajul lui: Bogdan Tataroiu din Iunie 28, 2009, 23:14:30

Cred ca ar trebui adaugate id-urile problemelor in numele topicurilor la fel ca pentru celelalte probleme.

S-a rezolvat.

Titlul: RÄƒspuns: 916 Trenuri
Scris de: Dragos-Alin Rotaru din Octombrie 01, 2010, 18:46:10

Nu inteleg ce as mai putea optimiza astfel incat sa iau 100 de puncte.

Fac ca in solutia oficiala, cu sortare, deque pt fiecare nod si programare dinamica pt fiecare muchie si cautarea binara din smenuri. Cei care au scos punctaj maxim, ce modificari ati adus ca sa scapati de TLE ?

Titlul: RÄƒspuns: 916 Trenuri
Scris de: Tirca Bogdan din Martie 09, 2011, 20:11:40

Ce nu ar fi bine in ideea asta:
Caut timpul binar(diferenta maxima minima dintre plecare si sosire) ,fac un dijkstra . Pentru fiecare nod pe care-l scot din coada(fie it o muchie care iese din nod)

daca trece de codul urmator relaxez muchia si sosire[it->y]=it->sosire;

Cod:

if(nod==1)
        sosire[nod]=it->plecare;
			
if(sosire[nod]>it->plecare)
	continue;
			
if(dif < it->plecare-sosire[nod])
	continue;
			
if(cost[it->y] <= cost[nod]+it->cost)
	continue;

Muchiile le retin exact cum se dau in fisierul de intrare.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Marius Stroe din Iunie 26, 2009, 22:05:09