Rezumat problemă

Fortificari

#4929

Unul dintre cele mai influente regate din continentul Alaocs este regatul Ofni. Harta regatului poate fi redată ca o matrice cu n linii și m coloane. Regatul este format din munți (^), râuri și lacuri (~), locuri libere de teren (_) și orașe (x). Observăm că se pot forma zone delimitate de munți, ape sau marginile hărții. Numim zonă o porțiune maximă de teren care conține locuri libere de teren și orașe, delimitată de munți, ape și marginea hărții. De asemenea, mai multe orașe învecinate pe linie sau pe coloană formează o cetate.

Din cauza puterii tot mai mari a regatelor rivale Etam și Akizif regele regatului Ofni a decis să înceapă un proces de fortificare a orașelor și cetăților. Pentru a face asta este necesară construcția de drumuri. Regele dorește ca între fiecare oraș și fiecare cetate să existe cel puțin un drum care să le lege și ca între toate cetățile să existe cel puțin un drum. Costul construcției unui drum printr-un loc liber are costul 1, construcția unui pod peste apă are costul 2, iar al unui tunel prin munte are costul 3. Pentru a nu goli trezoreria regală, regele își dorește ca acest cost de construcție a drumurilor să fie minim.

Problema are două cerințe.
Pentru c = 1, se cere determinarea numărului de cetăți, a numărului de zone și a numărului minim și maxim de cetăți dintr-o zonă.
Pentru c = 2, se cere costul total, minim, de construcție a drumurilor care conectează cetățile și orașele.

Fișiere Bacain Octavian-Tiberiu (Octavian2007) Bâcâin Octavian-Tiberiu dificilă

Clasa 11 Programare dinamică Probleme diverse de programare dinamică

Rezolvă

Detalii

Problema	Fortificari	Operații I/O	fortificari.in/fortificari.out
Limita timp	4.5 secunde	Limita memorie	Total: 64 MB / Stivă 8 MB
Id soluție	#64445101	Utilizator	Frățeanu Iustin (Alex_at_game)
Fișier	fortificari.cpp	Dimensiune	5.96 KB
Data încărcării	07 Mai 2026, 10:58	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

fortificari.cpp: In function ‘int fill2(int, int, int)’:
fortificari.cpp:34:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   34 |         auto [x, y] = q.top();
      |              ^
fortificari.cpp: In function ‘void fill(int, int, int)’:
fortificari.cpp:60:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   60 |         auto [x, y] = q.top();
      |              ^
fortificari.cpp: In function ‘void fillc22(int, int, int)’:
fortificari.cpp:91:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   91 |         auto [x, y] = q.top();
      |              ^
fortificari.cpp: In function ‘void fillc2(int, int, int)’:
fortificari.cpp:114:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  114 |         auto [x, y] = q.top();
      |              ^
fortificari.cpp: In function ‘int main()’:
fortificari.cpp:190:23: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  190 |             for (auto [r, c] : cel[i]) {
      |                       ^
fortificari.cpp:202:75: error: wrong number of template arguments (0, should be 1)
  202 |             priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
      |                                                                           ^
In file included from /usr/include/c++/13/string:49,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from fortificari.cpp:1:
/usr/include/c++/13/bits/stl_function.h:393:12: note: provided for ‘template<class _Tp> struct std::greater’
  393 |     struct greater : public binary_function<_Tp, _Tp, bool>
      |            ^~~~~~~
fortificari.cpp:202:76: error: template argument 3 is invalid
  202 |             priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
      |                                                                            ^~
fortificari.cpp:205:24: error: request for member ‘push’ in ‘pq’, which is of non-class type ‘int’
  205 |                     pq.push({dp[x][msk], x});
      |                        ^~~~
fortificari.cpp:209:24: error: request for member ‘empty’ in ‘pq’, which is of non-class type ‘int’
  209 |             while (!pq.empty()) {
      |                        ^~~~~
fortificari.cpp:210:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  210 |                 auto [d, x] = pq.top();
      |                      ^
fortificari.cpp:210:34: error: request for member ‘top’ in ‘pq’, which is of non-class type ‘int’
  210 |                 auto [d, x] = pq.top();
      |                                  ^~~
fortificari.cpp:211:20: error: request for member ‘pop’ in ‘pq’, which is of non-class type ‘int’
  211 |                 pq.pop();
      |                    ^~~
fortificari.cpp:219:46: error: ‘j’ was not declared in this scope
  219 |                     int nx = i + dx[p], ny = j + dy[p];
      |                                              ^
fortificari.cpp:227:28: error: request for member ‘push’ in ‘pq’, which is of non-class type ‘int’
  227 |                         pq.push({dp[nx * m + ny][msk], nx * m + ny});
      |                            ^~~~
fortificari.cpp:141:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  141 |     freopen("fortificari.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortificari.cpp:142:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  142 |     freopen("fortificari.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Cum funcționează evaluarea?