Mutacions de bacteris P16308


Statement
 

pdf   zip

thehtml

En un cert ecosistema conviuen n tipus de bacteris, identificats amb noms s1 < … < sn. Curiosament, els bacteris de cada tipus muten a un altre tipus després d’exactament un dia. Encara més curiosament, per a cada tipus de bacteri hi ha un altre tipus que muta a aquell tipus. És a dir, si denotem amb xy una mutació d’x a y, llavors en el conjunt de mutacions cada tipus apareix exactament una vegada com a x i una vegada com a y.

Donades les n mutacions i n instants de temps t1tn, digueu per a cada tipus si en quin tipus haurà mutat després de ti dies.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguida de les n mutacions, seguides dels n temps ti. Suposeu 1 ≤ n ≤ 104, que cada nom té entre una i cinc lletres minúscules, que no hi ha cap x ni cap y repetida, que cada x apareix com a y, i ‍0 ≤ ti ≤ 109.

Sortida

Per a cada cas, escriviu en què es transformarà cada tipus de bacteri si després de ti dies. Les transformacions han de sortir ordenades per si, i seguir el format de l’exemple. Escriviu una línia amb 20 guions després de cada cas.

Pista

Processeu el graf abans de llegir les ti. La solució esperada resol les n consultes de cada graf amb cost total Θ(n logn).

Public test cases
  • Input

    5
    d -> a
    e -> c
    b -> b
    a -> e
    c -> d
    1 10 6 4 0
    
    3
    zzzzz -> abcde
    abc -> abc
    abcde -> zzzzz
    12345678 1000000000 999999999
    

    Output

    a -> e
    b -> b
    c -> a
    d -> d
    e -> e
    --------------------
    abc -> abc
    abcde -> abcde
    zzzzz -> abcde
    --------------------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++