| Fişierul intrare/ieşire: | divinitate.in, divinitate.out | Sursă | ONI 2026, Baraj Seniori, ziua 2 |
| Autor | Adrian Andrei Rosu, Dan Constantin Spatarel | Adăugată de |  Ivan Andrei •IvanAndrei |
| Timp execuţie pe test | 2 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Divinitate
Pe îndepărtatul tărâm Algorithmicus, pacea este pe cale să se încheie...
Tărâmul este format din uscat şi apă. Uscatul este controlat în integralitate de K regate (numerotate de la 1 la K) în timp ce apa nu este controlată de niciun regat.
Tărâmul este reprezentat printr-o matrice D cu N linii şi M coloane. Fiecare celulă a sa conţine:
- fie un număr natural pozitiv reprezentând indicele regatului căruia îi aparţine, dacă celula corespunde unei zone de uscat a tărâmului;
- fie valoarea 0, dacă celula corespunde unei zone de apă a tărâmului.
Spunem că două celule se învecinează dacă au o latură comună.
Un lanţ de celule este o listă de celule cu proprietatea că oricare două celule consecutive din listă se învecinează.
Două regate A şi B se învecinează dacă se îndeplineşte cel puţin una dintre condiţiile:
- există o celulă a regatului A şi o celulă a regatului B care se învecinează;
- există o celulă a regatului A şi o celulă a regatului B care sunt capetele unui lanţ de celule format numai din celule de apă, cu excepţia capetelor.
Fiecare regat i are o putere de luptă proprie, descrisă printr-un întreg pozitiv, notat cu Vi.
Un regat A poate ataca un alt regat vecin B doar dacă puterea sa actuală este mai mare sau egală ca puterea regatului vecin (VA ≥ VB). După cucerirea regatului B, întregul său teritoriu devine parte din teritoriul regatului A, iar întreaga sa putere de luptă se adaugă la puterea totală a regatului A (adică VA ← VA + VB).
Un regat A poate cuceri regate succesiv, extinzându-şi teritoriul şi mărindu-şi puterea până când condiţia mai sus menţionată nu se mai îndeplineşte în raport cu niciun alt regat. În această situaţie, dacă regatul A nu ocupă deja întregul uscat, regele său (şi liderul bisericesc) poate invoca benevolenţa divinităţii, cerându-i să-i crească puterea regatului (VA) cu minimul necesar care să-i permită reluarea campaniei de cuceriri.
Cerinţe
Se dă un întreg C, numărul cerinţei de rezolvat, după cum urmează:
- Dacă C = 1 atunci se dau Q interogări de forma Si. Pentru fiecare dintre aceste interogări calculaţi, pornind de la starea iniţială, care este puterea maximă pe care regatul Si o poate atinge fără invocarea divinităţii. Ca excepţie, dacă regatul Si poate ocupa întregul uscat fără invocarea divinităţii, atunci răspunsul va fi 0.
- Dacă C = 2 atunci se dau Q interogări de forma (Si, Fi). Pentru fiecare dintre aceste interogări calculaţi, pornind de la starea iniţială, cantitatea minimă de putere pe care regatul Si trebuie să o primească din partea divinităţii pentru a reuşi să cucerească regatul Fi.
- Dacă C = 3 atunci se dau Q interogări de forma (Si, Fi). Pentru fiecare dintre aceste interogări calculaţi, pornind de la starea iniţială, numărul minim de situaţii în care divinitatea trebuie să-şi manifeste benevolenţa faţă de regatul Si pentru a reuşi să cucerească regatul Fi.
Date de intrare
Fişierul de intrare divinitate.in conţine pe prima linie întregii C, N, M şi K. Pe fiecare dintre următoarele N linii se află câte M întregi separaţi prin câte un spaţiu, reprezentând matricea D. Pe următoarea linie se află puterile iniţiale ale regatelor: V1, V2, ..., VK, separaţi prin câte un spaţiu.
Pe următoarea linie se află se află întregul Q. Fiecare dintre următoarele Q linii conţin unul sau doi întregi: S_i sau S_i şi F_i, în funcţie de C).
Date de ieşire
Fişierul de ieşire divinitate.out va conţine Q linii, linia i conţinând câte un număr întreg, răspunsul pentru interogarea i.
Restricţii
- 1 ≤ C ≤ 3
- 1 ≤ N, M ≤ 1 000
- 1 ≤ K ≤ N * M
- 0 ≤ Di,j ≤ K, pentru 1 ≤ i ≤ N şi 1 ≤ j ≤ M
- 1 ≤ Q ≤ 300 000
- 1 ≤ Vi ≤ 1018, pentru 1 ≤ i ≤ K
- 1 ≤ Si, Fi ≤ K şi Si ≠ Fi, pentru 1 ≤ i ≤ Q
- Un regat poate fi format din mai multe zone izolate pe hartă (exclave). Cucerirea unei exclave implică cucerirea întregului regat.
- Se garantează că iniţial fiecare dintre cele K regate controlează cel puţin o celulă.
- Apa nu aparţine niciunui regat, nu poate fi cucerită de vreun regat şi poate fi privită strict ca pe o cale de deplasare.
Tabelul de mai jos reprezintă distribuţia de punctaj în funcţie de restricţii şi cerinţă:
| # | Restricţii | C = 1 | C = 2 | C = 3 |
|---|---|---|---|---|
| 1 | N ≤ 100, M ≤ 100, Q ≤ 100, Di,j ≠ 0 pentru 1 ≤ i ≤ N şi 1 ≤ j ≤ M | 1 | 2 | 3 |
| 2 | N ≤ 100, M ≤ 100, Q ≤ 30 000, Di,j ≠ 0 pentru 1 ≤ i ≤ N şi 1 ≤ j ≤ M | 2 | 3 | 4 |
| 3 | N ≤ 100, M ≤ 100, Q ≤ 100 | 2 | 3 | 4 |
| 4 | N ≤ 100, M ≤ 100, Q ≤ 30 000 | 2 | 3 | 4 |
| 5 | Oricare două regate se învecinează | 5 | 9 | 13 |
| 6 | Q ≤ 30 000 | 4 | 6 | 9 |
| 7 | Fără alte restricţii | 4 | 7 | 10 |
Exemplu
| divinitate.in | divinitate.out |
|---|---|
| 1 5 5 6 6 1 1 0 2 1 1 0 0 2 1 0 0 2 2 0 0 3 4 4 5 5 4 4 6 100 2 3 3 1 7 6 1 2 3 4 5 6 | 0 16 16 16 1 16 |
| 2 5 5 6 6 1 1 0 2 1 1 0 0 2 1 0 0 2 2 0 0 3 4 4 5 5 4 4 6 100 2 3 3 1 7 6 1 4 2 1 3 1 4 3 5 1 6 2 | 0 84 84 0 84 0 |
| 3 5 5 6 6 1 1 0 2 1 1 0 0 2 1 0 0 2 2 0 0 3 4 4 5 5 4 4 6 100 2 3 3 1 7 6 1 4 2 1 3 1 4 3 5 1 6 2 | 0 1 1 0 2 0 |
Explicaţii
Regatul 6 este format din două exclave. Cucerirea uneia conduce la cucerirea imediată a celeilalte.
Primul regat poate cuceri toate celelalte regate fără invocarea divinităţii şi va avea o putere finală de 116. Ca excepţie, răspunsul afişat pentru prima cerinţă va fi 0.
Regatele 2, 3, 4 şi 6 pot cuceri toate celelalte regate cu excepţia primului regat fără invocarea divinităţii. La acel moment ele ar avea puterea 16.
Al cincilea regat nu poate cuceri niciun alt regat fără invocarea divinităţii. Pentru a putea cuceri primul regat sunt necesare două invocaţii ale divinităţii. După prima invocare, regatului îi creşte puterea cu 1. După a doua invocare, regatului îi creşte puterea cu încă 83.
