eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Козак Вус і найкраща країна

Козак Вус і найкраща країна

Ліміт часу 5 секунд
Ліміт використання пам'яті 1024 MiB

Козак Вус нарешті знайшов країну своєї мрії. Вона складається з n міст, між якими не проходить жодна дорога. Звичайно, Вус захотів виправити цю ситуацію, і тому придумав m різних двосторонніх доріг, які можна було би прокласти. За його задумом кожна дорога з'єднує два різні міста. Але виникла проблема: кожне місто i може виділити на побудову доріг c_i копійок, а для кожної дороги j на її побудову пішло б w_j копійок. Тому Козак вирішив, що йому вистачить побудувати декілька доріг так, аби всі міста стали сусідами. Міста називаються сусідами, якщо можливо дорогами країни дістатися з одного міста в інше.

При плануванні своїх робіт Козак Вус зрозумів одну річ: коли він будуватиме чергову дорогу, міста будуть об'єднуватися в групи сусідів. Щоб побудувати j-ту дорогу, потрібно, щоб міста (або їх сусіди), між якими будується дорога, сумарно мали принаймні w_j копійок (адже спершу потрібно заплатити за дорогу й лише потім будувати). Після побудови дороги бюджети міст об'єднуються, а вартість дороги вираховується з нової спільної казни.

Для кожного з n міст ви знаєте число c_i — кількість копійок, які може витратити місто i. Для кожної з m доріг ви знаєте числа v_i, u_i та w_i, які означають, що дорога i з'єднує міста v_i та u_i, а на її побудову потрібно w_i копійок. Скажіть, чи можливо вибрати певну кількість доріг та впорядкувати їх так, щоб усі міста стали сусідами. А якщо це можливо, то знайдіть послідовність доріг, у якій їх потрібно будувати.

Вхідні дані

Перший рядок містить три цілі числа n, m та g (1 \leq n \leq 10^6, 0 \leq m \leq 10^6, 0 \leq g \leq 7) — кількість міст, кількість доріг та номер блока відповідно.

Наступний рядок містить n цілих чисел c_1, c_2, \ldots, c_n (1 \leq c_i \leq 10^6) — початкова кількість копійок в i-му місті.

Кожний із наступних m рядків містить по три цілі числа v_i, u_i та w_i (1 \leq v_i,u_i \leq n, 1 \leq w_i \leq 10^6) — номер міст, між якими i-та дорога, та ціна її побудови відповідно.

Протокол взаємодії

Для того, щоб показати дороги, які потрібно побудувати, використовуйте таку функцію:

void add(integer i)
  • Ця функція будує дорогу під номером i (1\leq i \leq m).

Вам потрібно реалізувати одну функцію:

boolean solve(integer n, integer m, integer g, array of integers c, array of integers v,
              array of integers u, array of integers w)
  • n — кількість міст у країні;

  • m — кількість доріг, які можна прокласти;

  • g — номер блока;

  • c_i (|c|=n) — початкова кількість копійок у i-тому місті;

  • v_i та u_i (|v|=|u|=m) — номери вершин, що з'єднує i-та дорога;

  • w_i (|w|=m) "— кількість копійок, необхідних на побудування i-тої дороги;

  • ця функція повинна повертати true, якщо можливо правильно вибрати послідовність доріг, і false, якщо ні.

Якщо ваша функція повертає true, то до того, як вона його поверне, вона має зробити виклики функції add для всіх побудованих доріг у тому порядку, у якому вони побудуються.

Вихідні дані

Якщо функція повертає false, то в першому рядку буде виведено одне число -1.

Інакше в першому рядку буде виведено число q — кількість побудованих доріг. У наступних q рядках буде виведено по одному число x — номер побудованої дороги.

Приклад

Вхідні дані #1
4 5 0
2 5 2 4
1 2 7
3 4 4
1 4 5
4 2 3
3 2 4
Вихідні дані #1
3
4
2
3
Вхідні дані #2
3 3 0
6 2 5
2 3 9
2 1 5
1 3 10
Вихідні дані #2
-1

Примітка

У першому прикладі країна складається з 4-ох міст, а план Козака Вуса складається з 5-и доріг. Спочатку будується дорога під номером 4: міста 2 та 4 об'єднаються у групу, а з їхнього загального бюджету сплачується 3 копійки. На рахунку цієї групи залишається 6 копійок. Після побудови дороги під номером 2 бюджет групи буде складати 4 копійки, адже приєдналося місто 3 з бюджетом у 2 копійки, а також витратили 4 копійки на побудову дороги. Після побудови 3-ої дороги всі міста стануть сусідами, а їх загального бюджету вистачить, щоб заплатити 5 копійок за дорогу.

У другому прикладі неможливо вибрати дороги та порядок їх побудови так, щоб усі міста стали сусідами й щоб за усі дороги було заплачено.

Оцінювання

  1. (3 балів) n \leq 10; m = n - 1; c_i = 1; w_i = 1; якщо побудувати всі m доріг, усі міста стануть сусідами;

  2. (8 балів) n,m \leq 10;

  3. (12 балів) n,m \leq 10^5; c_i = 1;

  4. (14 балів) n,m \leq 10^5; усі w_i однакові;

  5. (16 балів) n,m \leq 10^3;

  6. (19 балів) n,m \leq 10^5;

  7. (12 балів) n,m \leq 5 \cdot 10^5;

  8. (16 балів) без додаткових обмежень.

Автор Mark Grishechkin