251 Mine

[ditzone]

Aici puteţi discuta despre problema Mine.

[•wefgef]

ar fi fain daca nu ati pune limitele la unele probleme asa stranse.

in pascal citirea ia mai mult si chiar e greu de scos 100 pe ele.

un 0.1 in plus la limita  nu afecteaza cu nimic, ca doar nu intra brute-ul

[andreit1]

Lasa ca invatam si noi sa parsam citirea... sau si mai bine sa renuntam la pascal!

[•greco]

Limita a fost de 0.1 secunde initial.

[•wefgef]

Lasa ca invatam si noi sa parsam citirea...

asta am si facut .

[cristi8]

iau doar 20 pct (in rest WA si pe vreo 4-5 teste (din 25) iau TLE) si nu stiu de ce.
eu tin un min-heap cu nodurile in care se poate ajunge, ordonat dupa costul muchiei care duce in ele.
la fiecare valoare "q" citita iau din heap primul element cat timp costul e mai mic sau egal cu valoarea citita, si adaug in heap toti vecinii nodului/nodurilor extrase.
Am grija sa marchez nodurile "relaxate", si cum am marcat nodul n opresc algoritmul.

----
alta exprimare, poate mai clara:
la fiecare valoare "q" citita (intr-o anumita stare), exista:
 - o submultime de noduri in care se poate ajunge (un vector u[] de 0 sau 1)
 - o alta submultime de noduri: vecini ai primei submultimi (retinut ca un min-heap in functie de costul muchiei).
ca sa trec de la o stare la alta, iau din a 2a multime (din heap) elementele cu costul <= decat "q" si le adaug la prima multime. bine-nteles, reimprospatez tot-odata si heap-ul cu noile noduri si costuri.
----

ce gresesc?

PS:
daca citesc muchiile cu:

Cod:

  fgets(buf, 100, stdin);
  sscanf(buf, "%d%d%d", &v1, &v2, &c);

dureaza mai mult decat:

Cod:

  scanf("%d%d%d", &v1, &v2, &c);

e normal?

[•wefgef]

ai grija sa introduci vecinii nodurilor vizitate abia dupa ce termini de scos din heap?

[cristi8]

nu, de ce ?
uite cum fac:

Cod:

void foo(int val) {
  int x;
  vnod *q;
  while(h[1].c <= val && hn) {
    x = h[1].x;
    h[1] = h[hn--];
    hdown(1);
    if(!u[x]) {
      u[x] = 1;
      for(q = lv[x]; q; q = q->nxt)
        if(!u[q->x])
          hadd(q->x, q->c);
    }
  }
}

unde lv(i) e lista de vecini a nodului i, h e heap-ul (structura cu { int x, c; } reprezentand nodul si costul). hn e dimensiunea heap-ului

[•pauldb]

In ce complexitate se rezolva problema? 

[u-92]

eu am facut (M+N)*logN

[•pauldb]

Eu am reusit sa scot (M+N) * log M...si iau TLE pe 6 teste. Ce inseamna sa "parsezi" citirea? 

[•greco]

Citesti sub forma de string o linie intreaga si calculezi singur valorile din ea prin inmultiri cu 10 si adunari repetate. Cam infect, dar uneori mai e nevoie si de asa ceva. La fel se poate parsa si scrierea, insa eu unul am avut nevoie de scriere optimizata la o singura problema pana acum (de pe SGU cred).

[•stocarul]

Are ceva mai special testul 6?
Primesc 96 pct,cu WA pe testul 6 
Ce poate fi ?

[•savim]

Imi puteti da va rog o idee cum sa fac o citire mai rapida la problema asta?
Eu am incercat sa citesc cu fread tot fisierul intr-un string, si apoi sa lucrez pe acesta. Daca imi las doar citirea in program iau un TLE pe unul din ultimele 2 teste.    http://infoarena.ro/job_detail/351561

[•bogdan2412]

Poti face functia read_file() inline si, de asemenea, poti folosi un pointer la pozitia curenta in sir, in loc de un int.

Un exemplu pentru toata lumea:

Cod:

char *p = s;

inline int read_value() {
    int val = 0;
    for (; '0' <= *p && *p <= '9'; p++)
        val = val * 10 + *p - '0';
    p++;
    return val;
}

a = read_value(); b = read_value();

Facand modificarile astea 2, sursa ta (fara rezolvare, doar citire) intra in timp in 190 ms . Aparent, nu citirea dureaza cel mai mult la tine, ci ce faci cu vectorul arb in functia cit. Cred ca spargi cache-ul parcurgandu-l in ordine inversa. Incearca sa folosesti altceva decat arbori de intervale.

[•savim]

Merci de sfat. Am folosit citirea prezentata de tine, insa ca optimizare am tinut graful fara vectori (o lista cu muchii, si pentru fiecare nod sa tin minte de unde ii incep muchiile).