Marele Premiu al Saratovului - Codeforces

Marele Premiu de la Saratov

Cum se rezolvă C și D?
Cred că am mai văzut problema J undeva

fmota
Acum 3 ani
37

Cum se rezolvă E și H? Amândoi sunt o problemă destul de interesantă.

În primul rând, putem întreba interogări pentru a găsi toate frunzele copacului. Pentru a verifica dacă un vârf este o frunză, cerem o interogare care conține toate - 1 alte vârfuri; dacă răspunsul este - 1, vârful pe care l-am exclus dintr-o interogare este o frunză.

Atunci să ne înrădăcinăm arborele la o frunză. Lăsa L(X) fie setul de frunze din subarborele vârfului X . Deoarece nu există vârfuri cu gradul 2, pentru oricare două vârfuri X și y L(X) ≠ L(y); în plus, X este un strămoș al y dacă nu. Deci, dacă obținem informații despre L(X) pentru fiecare vârf, atunci putem reconstrui copacul.

Pentru rădăcină, L(rădăcină) este ansamblul tuturor frunzelor. Pentru fiecare altă frunză z, L(z) = z>. Deci, trebuie să găsim L(X) numai pentru non-frunze. Pentru a verifica dacă o frunză z se află într-un subarbore de vârf non-frunze y, s-ar putea să ne întrebăm 3 rădăcină y z .

Deci, dacă numărul de frunze este l, trebuie să întrebăm (l - 1) - l) interogări de găsit L(X) pentru toate vârfurile care nu sunt frunze. Aceasta nu va depăși 2450 și, prin urmare, nu vom solicita mai mult de 2550 de interogări.

Misto! Este o soluție foarte simplă.

Am avut o soluție pentru aceleași interogări, dar a doua parte a folosit o perspectivă diferită.

Deci, pentru fiecare frunză cunoaștem „calea” către rădăcină (numai vârfuri, nu ordinea lor). Acum, intersecția oricăror două astfel de „căi” este, de asemenea, o cale către rădăcină de la un anumit vârf (lca lor). Și fiecare vârf este lca de 2 frunze (din cauza lipsei vârfurilor de 2 grade). Deci, acum avem o listă de "căi" pentru toate vârfurile și trebuie să reconstituim un copac care poate fi realizat de dfs simpli.

Dacă arborele este un bambus, răspunsurile pentru toate interogările din prima parte a algoritmului ar trebui să fie - 1, nu ar trebui? Dacă nu, vă rugăm să explicați de ce.

E: În DAG fiecare nod poate fi atins de A și ajunge la B, dacă nu

A nu are un nivel de licență
B nu are o clasă superioară
| indegree | > = 1 și | outdegree | > = 1 pentru toate nodurile care nu sunt A, B

Acum ar trebui să selectați două seturi de margini disjuncte EA, EB astfel încât

marginile din EA au puncte finale distincte
muchiile din EB au puncte de pornire distincte

Acest lucru poate fi găsit prin potrivirea maximă în Oh(pl 0,5)

Uau, curge pentru 1000000 de margini, acesta este un nou record pe care l-am văzut vreodată:)

Apropo, poate fi rezolvat fără flux.

Nu înțeleg de ce este o nouă înregistrare pentru dvs., dar potrivirea bipartită pe vârfurile 10 ^ 6 ar trebui să ruleze în mod evident la timp:)

Ștergerea graficului pentru fiecare TC a fost totuși o durere.

De asemenea, se poate face în O (m) și chiar se poate face cu costul total minim al muchiilor în timp O (m).

Să adăugăm două muchii de la B la A. Acum avem doar o condiție pe grade. Să obținem un grpah bipartit cu 2 copii de vârfuri în partea stângă (corespunzătoare vârfului în EA și vârfului în EB) și muchii în partea dreaptă. Fiecare vârf din partea a doua va avea exact două margini (pentru a începe în EA și în și în EB). Problema este de a găsi potrivirea perfectă (prin partea din stânga) în acest grafic.