Rezumat problemă

Amazon

#4565

România este formată din N orașe conectate între ele, existând un traseu unic între oricare două orașe. Un traseu este o secvență de drumuri care conectează două orașe, astfel încât niciun drum nu se repetă. În total, există N−1 drumuri bidirecționale care conectează orașele.

Fiecare drum are și un cost asociat. Echipa lui Jeffrey a creat o lista de M perechi de orașe între care se va circula foarte des pentru livrarea coletelor. Definim costul unei perechi de orașe (x, y) ca fiind suma costurilor drumurilor din traseul de la orașul x la orașul y. De asemenea, definim costul total ca fiind suma tuturor costurilor celor M perechi de orașe date.

Jeffrey poate să aplice următorul tip de operație: selectează un drum cu un cost strict pozitiv și îi scade costul cu 1. Din motive de “frugality”, această operație poate fi aplicată de cel mult K ori, unde K este un număr natural.

Se cere să găsiți costul total minim ce poate fi obținut, după aplicarea de cel mult K ori a operației menționate mai sus.

Concursul Interjudețean de Matematică și Informatică Grigore Moisil, 2023

Fișiere Moldovan Robert (moldovan_robert_lol) Robert-Raul Borcani, Octavian Trifan, Daniel Todașcă concurs

Clasa 11 Teoria Grafurilor Arbori cu rădăcină Lowest Common Ancestor Smenul lui Mars (Difference Arrays) Heavy-Light Decomposition

Rezolvă

Detalii

Problema	Amazon	Operații I/O	amazon.in/amazon.out
Limita timp	1 secunde	Limita memorie	Total: 256 MB / Stivă 64 MB
Id soluție	#63676893	Utilizator	Moldovan Mihai (mihai_moldovan)
Fișier	amazon.cpp	Dimensiune	2.81 KB
Data încărcării	13 Martie 2026, 22:19	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

amazon.cpp:17:26: error: 'int log2 [200001]' redeclared as different kind of symbol
     pow2[20], log2[200001], mars[200001], cost[200001];

                          ^
In file included from /usr/include/features.h:374:0,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/os_defines.h:39,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/c++config.h:426,
                 from /usr/include/c++/4.8/iostream:38,
                 from amazon.cpp:1:
/usr/include/i386-linux-gnu/bits/mathcalls.h:144:1: error: previous declaration of 'double log2(double)'
 __MATHCALL (log2,, (_Mdouble_ __x));
 ^
amazon.cpp: In function 'void construct_rmq()':
amazon.cpp:45:19: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
             log2[i] = log2[i >> 1] + 1;

                   ^
amazon.cpp:45:34: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
             log2[i] = log2[i >> 1] + 1;

                                  ^
amazon.cpp: In function 'int query(int, int)':
amazon.cpp:70:21: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
     int t = log2[dif];

                     ^

Cum funcționează evaluarea?