Rezumat problemă

gcd_tree

#4670

RAU-Gigel și Vlad sunt prieteni buni și le place tot timpul să se provoace unul pe altul. De data aceasta, RAU-Gigel a inventat o problemă interesantă de matematică.

Acesta are un arbore secret cu N noduri (numerotate de la 1 la N), în care fiecare nod are asociată o valoare (pe lângă numărul său de ordine din arbore), care este un număr natural și ii spune lui Vlad informații despre unele drumuri din acest arbore. O informație are forma x, y, val și reprezintă faptul că lanțul din arbore de la nodul x la nodul y are cel mai mare divizor comun al valorilor asociate nodurilor acestuia egal cu val, unde val este un număr natural nenul.

Vlad știe că RAU-Gigel minte câteodată și s-ar putea ca unele dintre restricțiile date să fie eronate, astfel că vrea să afle întâi folosind informațiile ce le are la îndemână dacă ar putea exista un arbore care să respecte toate restricțiile date de prietenul său.

Pentru că știe ce programator iscusit ești, Vlad ți-ar fi foarte recunoscător daca l-ai putea ajuta cu această problemă prin a scrie un program care să o rezolve cât mai eficient.

RAU-Coder 2024

Fișiere Lorintz Alexandru (Alex_tz307) Alexandru Lorintz concurs

Clasa 11 Structuri de date arborescente Structuri de date Arbori de intervale Algoritmul lui Euclid Range Minimum Query Lowest Common Ancestor Heavy-Light Decomposition

Rezolvă

Detalii

Problema	gcd_tree	Operații I/O	gcd_tree.in/gcd_tree.out
Limita timp	2 secunde	Limita memorie	Total: 256 MB / Stivă 64 MB
Id soluție	#55358361	Utilizator	Gelu Ionescu (test111)
Fișier	gcd_tree.cpp	Dimensiune	3.03 KB
Data încărcării	12 Ianuarie 2025, 17:31	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

gcd_tree.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
 #warning That's the baby, that's not my baby

  ^
gcd_tree.cpp:10:21: warning: missing terminating ' character [enabled by default]
 const int NMAX = 100'000;

                     ^
gcd_tree.cpp:10:1: error: missing terminating ' character
 const int NMAX = 100'000;

 ^
gcd_tree.cpp:11:1: error: expected ',' or ';' before 'const'
 const int LOG = 16;

 ^
gcd_tree.cpp:24:10: error: 'LOG' was not declared in this scope
 int jump[LOG + 1][NMAX + 1];

          ^
gcd_tree.cpp:25:8: error: 'LOG' was not declared in this scope
 int up[LOG + 1][NMAX + 1];

        ^
gcd_tree.cpp: In function 'int lca(int, int)':
gcd_tree.cpp:31:16: error: 'LOG' was not declared in this scope
   for (int k = LOG; k >= 0; k--) {

                ^
gcd_tree.cpp:33:11: error: 'jump' was not declared in this scope
       u = jump[k][u];

           ^
gcd_tree.cpp:39:16: error: 'LOG' was not declared in this scope
   for (int k = LOG; k >= 0; k--) {

                ^
gcd_tree.cpp:40:9: error: 'jump' was not declared in this scope
     if (jump[k][u] != jump[k][v]) {

         ^
gcd_tree.cpp:45:10: error: 'jump' was not declared in this scope
   return jump[0][u];

          ^
gcd_tree.cpp: In function 'int gcdPath(int, int)':
gcd_tree.cpp:51:16: error: 'LOG' was not declared in this scope
   for (int k = LOG; k >= 0; k--) {

                ^
gcd_tree.cpp:53:29: error: 'up' was not declared in this scope
       ret = std::__gcd(ret, up[k][u]);

                             ^
gcd_tree.cpp:54:11: error: 'jump' was not declared in this scope
       u = jump[k][u];

           ^
gcd_tree.cpp:57:29: error: 'up' was not declared in this scope
       ret = std::__gcd(ret, up[k][v]);

                             ^
gcd_tree.cpp:58:11: error: 'jump' was not declared in this scope
       v = jump[k][v];

           ^
gcd_tree.cpp: In function 'void dfs(int, int)':
gcd_tree.cpp:70:7: error: 'jump' was not declared in this scope
       jump[0][v] = u;

       ^
gcd_tree.cpp: In function 'void solve()':
gcd_tree.cpp:91:14: error: expected unqualified-id before '[' token
   for (auto &[x, y, c] : restrictions) {

              ^
gcd_tree.cpp:91:14: error: expected ';' before '[' token
gcd_tree.cpp:91:15: error: 'x' was not declared in this scope
   for (auto &[x, y, c] : restrictions) {

               ^
gcd_tree.cpp:91:18: error: 'y' was not declared in this scope
   for (auto &[x, y, c] : restrictions) {

                  ^
gcd_tree.cpp:91:21: error: 'c' was not declared in this scope
   for (auto &[x, y, c] : restrictions) {

                     ^
gcd_tree.cpp: In lambda function:
gcd_tree.cpp:91:24: error: expected '{' before ':' token
   for (auto &[x, y, c] : restrictions) {

                        ^
gcd_tree.cpp: In function 'void solve()':
gcd_tree.cpp:91:24: error: expected ';' before ':' token
gcd_tree.cpp:91:24: error: expected primary-expression before ':' token
gcd_tree.cpp:91:24: error: expected ')' before ':' token
gcd_tree.cpp:91:24: error: expected primary-expression before ':' token
gcd_tree.cpp:91:24: error: expected ';' before ':' token
gcd_tree.cpp:95:24: error: 'LOG' was not declared in this scope
   for (int k = 1; k <= LOG; k++) {

                        ^
gcd_tree.cpp:97:7: error: 'jump' was not declared in this scope
       jump[k][i] = jump[k - 1][jump[k - 1][i]];

       ^
gcd_tree.cpp:102:22: error: expected unqualified-id before '[' token
     for (const auto &[u, v, c] : restrictions) {

                      ^
gcd_tree.cpp:102:22: error: expected ';' before '[' token
gcd_tree.cpp:102:23: error: 'u' was not declared in this scope
     for (const auto &[u, v, c] : restrictions) {

                       ^
gcd_tree.cpp:102:26: error: 'v' was not declared in this scope
     for (const auto &[u, v, c] : restrictions) {

                          ^
gcd_tree.cpp:102:29: error: 'c' was not declared in this scope
     for (const auto &[u, v, c] : restrictions) {

                             ^
gcd_tree.cpp: In lambda function:
gcd_tree.cpp:102:32: error: expected '{' before ':' token
     for (const auto &[u, v, c] : restrictions) {

                                ^
gcd_tree.cpp: In function 'void solve()':
gcd_tree.cpp:102:32: error: expected ';' before ':' token
gcd_tree.cpp:102:32: error: expected primary-expression before ':' token
gcd_tree.cpp:102:32: error: expected ')' before ':' token
gcd_tree.cpp:102:32: error: expected primary-expression before ':' token
gcd_tree.cpp:102:32: error: expected ';' before ':' token
gcd_tree.cpp:153:1: error: expected '}' at end of input
 }
 ^
gcd_tree.cpp:153:1: error: expected '}' at end of input
gcd_tree.cpp: In function 'int lca(int, int)':
gcd_tree.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

 ^

Cum funcționează evaluarea?