#1118
Clepsidra
Un graf conex cu N
noduri și M
muchii poate fi privit ca o clepsidră cu centrul în nodul X
, 1 ≤ X ≤ N
, dacă putem împărți toate nodurile, mai puțin nodul X
, în două submulțimi nevide astfel încât orice drum de la un nod dintr-o mulțime la un nod din cealaltă mulțime trece prin nodul X
. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele N
noduri alese drept centru, modulo 666013
. Două moduri se consideră distincte dacă cele două submulțimi aferente sunt diferite. Ordinea submulțimilor într-un mod este relevantă, dar ordinea nodurilor în cadrul unei mulțimi nu este. Spre exemplu, soluțiile ({1,2,3}, {4,5})
şi ({4,5}, {1,2,3})
sunt distincte, dar soluţiile ({4,5}, {1,2,3})
şi ({4,5}, {1,3,2})
nu sunt distincte.
ONI 2014, Clasele XI-XII
Problema | Clepsidra | Operații I/O |
clepsidra.in /clepsidra.out
|
---|---|---|---|
Limita timp | 0.5 secunde | Limita memorie |
Total: 32 MB
/
Stivă 8 MB
|
Id soluție | #33409034 | Utilizator | |
Fișier | clepsidra.cpp | Dimensiune | 1.81 KB |
Data încărcării | 17 Decembrie 2021, 15:53 | Scor / rezultat | Eroare de compilare |
clepsidra.cpp: In function 'void dfs(int)': clepsidra.cpp:23:27: error: expected ']' before ';' token niv[nc]=niv[tati[nc]+1; ^ clepsidra.cpp:25:27: error: invalid use of member function (did you forget the '()' ?) for (int i=0; i<a[nc].size; i++) ^ clepsidra.cpp:32:17: error: incompatible types in assignment of 'const int' to 'int [200001]' nmin=min(nmin[nc], niv[nc]); ^ clepsidra.cpp: In function 'int main()': clepsidra.cpp:65:14: error: 'class std::vector<int>' has no member named 'push' a[x].push(y); //lista de adiacenta ^ clepsidra.cpp:66:14: error: 'class std::vector<int>' has no member named 'push' a[y].push(x); ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Clepsidra face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.