SIO Gradovi

Interfejs

Pošaljite jedan C++23 izvorni fajl koji implementira sledeći interfejs:

void Gradovi(int N, int M, int K, int Q, int* U, int* V, int* G, int* S);

Tekst zadatka

У држави Бајтовији постоји места која су повезана са двосмерних путева. Гарантује се да је могуће стићи од било којег места до N M

било ког другог места коришћењем једног или више путева. Пут повезује места и и има дужину . од датих места су i U [i] V [i] 2 i K N

градови, док су преостала села. Изолованост неког села је растојање до најближег града. У циљу развоја, краљ Бајтовије жели да нека од датих села прогласи градовима, тако да се изолованост најизолованијег села минимизује. У оквиру буџета Бајтовије, влада је одобрила проглашавање тачно села у градове. Q

Пронађите села која треба прогласити градовима, тако да се изолованост најизолованијег села минимизује. Уколико има више решења, пронађите било које. Описи функција Потребно је да имплементирате функцију Gradovi(N , M , K, Q, U […], V […], G[…], S[…])

Ова функција ће бити позвана једном по примеру. Број представља број места у Бајтовији, број путева, је број градова, док је N M K

Q број села која је потребно прогласити градовима. Низови и дужине представљају места која су повезана. Низ дужине U V M G K

представља листу градова. У низ је потребно уписати села која ће бити проглашена градовима. Сви низови су индексирани од 1. Пример S Q

Нека је . У овом примеру постоје града, а N = 5, M = 5, K = 2, Q = 1, U = {1, 2, 3, 4, 5}, V = {2, 3, 4, 2, 4}, G = {2, 4} 2

једно село је потребно прогласити градом. Уколико место прогласимо градом, најизлованије село постаје село са изолованошћу 5 3

. Ограничења 2 2 = 4

2 ≤ N , M ≤ 200.000

0 ≤ K ≤ N 1 ≤ Q ≤ N

1 ≤ K + Q ≤ N

1 ≤ Ui ≠ Vi ≤ N

Бајтовија је повезана Сваки пут повезује различит пар градова Подзадаци Тест примери су подељени у подзадатака: [4 поена]: , пут повезује места и , за , а пут повезује место и место 6

[9 поена]: , путеви повезују места циклично (тј. путеви су пермутација путева из претходног подзадатка) M = N, Q = 1 i i i + 1 i < N N N 1

[11 поена]: M = N, Q = 1

[28 поена]: K = 1, Q = 1

[12 поена]: Q = 1

[36 поена]: Нема додатних ограничења N , Q ≤ 1.000

Детаљи имплементације Потребно је да пошаљете тачно један фајл који имплементира поменуту функцију. Осим тражене функције, ваш фајл може gradovi.cpp садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке. Ваша функција мора бити следећег облика: void Gradovi(int N, int M, int K, int Q, int* U, int* V, int* G, int* S); Вашим програмима је дозвољено да мењају садржај низова али не смеју да приступају ван граница датих низова. Уз задатак, обезбеђен вам је "template" фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке: У првом реду бројеве . У наредних редова по броја и . N , M , K, Q

У наредном реду вредности које представљају елементе низа . M 2 U [i] V [i]

K G

Затим овај програм зове вашу функцију и исписује вредности S[1], S[2], . . . , S[Q] , које ваша функција упише у њега.