| Fişierul intrare/ieşire: | muchiipermutate.in, muchiipermutate.out | Sursă | Lot Bistrița Seniori 2026, Baraj 3 |
| Autor | Alexandru Lorintz | Adăugată de |  Bogdan Vlad-Mihai •bogdanvladmihai |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Muchii Permutate
Se dă un arbore cu N noduri (numerotate de la 1 la N) şi considerăm muchiile sale numerotate de la 1 la N - 1 (în ordinea în care sunt date în input). Un arbore este un graf neorientat, conex şi aciclic.
Fie P o permutare a numerelor de la 1 la N - 1. Pentru această permutare P dată, atribuim fiecărei muchii de index i o pondere egală cu P[i]. Apoi, considerăm un algoritm în care iniţial nu avem nicio muchie în arbore şi începem să le adăugăm una câte una, în ordinea numerotării lor (practic în ordinea în care sunt date în input, de la 1 la N - 1 - ordinea de adăugare nu depinde de ponderi).
Pentru ca permutarea P să fie considerată validă, la fiecare pas din algoritm se cere ca orice componentă conexă maximală (cu cel puţin 2 noduri) formată până acum să aibă doar muchii cu ponderi consecutive - aici componentele sunt considerate individual (şi doar cele maximale), deci toate trebuie să respecte condiţia, la orice pas al algoritmului.
Cerinţă
Dându-se numărul N, reprezentând numărul de noduri din arbore, respectiv cele N - 1 muchii ale arborelui (în ordinea din enunţ), să se determine numărul minim de inversiuni dintr-o permutare validă, precum şi numărul de permutări valide care ating acest minim (modulo 10^9 + 7).
Detalii de implementare
Concurenţii vor avea de implementat o singură funcţie:
std::pair<long long, int> solve(int N, std::vector<int> U, std::vector<int> V);care primeşte ca parametri:
- N, numărul de noduri din arbore;
- Şirurile U şi V, unde perechea U[i], V[i] reprezintă capetele muchiei i + 1 din arbore (după numerotarea din enunţ), pentru i de la 0 la N - 2.
Funcţia solve va fi apelată o singură dată.
Din cauza limitărilor impuse de infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de aici .
Totodată, unele teste au fost omise. Prin urmare, în situaţii rare pot exista diferenţe între punctajul de pe inforarena şi punctajul care s-ar fi obţinut în concurs .
Restricţii
- 2 ≤ N ≤ 500 000
- 1 ≤ Ui, Vi ≤ N, pentru 0 ≤ i ≤ N - 2
- Atenţie: Doar numărul de permutări valide care au un număr minim de inversiuni se calculează modulo 10^9 + 7. Pentru numărul minim de inversiuni se calculează valoarea exactă.
Punctare
| Subtask | Punctaj | Constrângeri |
|---|---|---|
| 1 | 2 puncte | N ≤ 200 000 şi arborele dat are formă de stea (există un nod de grad N - 1) |
| 2 | 4 puncte | N ≤ 10 |
| 3 | 11 puncte | N ≤ 500 |
| 4 | 13 puncte | N ≤ 5 000 |
| 5 | 21 puncte | N ≤ 200 000 şi arborele este un lanţ (toate nodurile au gradul cel mult 2) |
| 6 | 22 puncte | N ≤ 200 000 |
| 7 | 27 puncte | Fără restricţii suplimentare |
Exemple
| Fişier de intrare | Fişier de ieşire |
|---|---|
| 7 3 7 2 5 2 6 1 3 1 2 2 4 | 2 2 |
| 20 16 17 4 5 8 9 11 12 18 19 1 2 14 15 7 8 19 20 6 7 15 16 3 4 12 13 9 10 2 3 17 18 5 6 10 11 13 14 | 48 8 |
Explicaţii
Pentru primul exemplu, cele două permutări valide optime care respectă constrângerile şi obţin minimul de 2 inversiuni sunt:
- P = (1, 3, 4, 2, 5, 6)
- P = (3, 1, 2, 4, 5, 6)
Pentru al doilea exemplu, numărul minim de inversiuni al unei permutări valide este 48 şi există 8 permutări valide cu acest număr minim de inversiuni.
