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

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

5 секунд

1 024 мегабайти

Легка

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

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

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

Вхідні дані

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

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

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

Взаємодія

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

void add(integer i)

Ця функція будує дорогу під номером $i$ ( $1 \leq i \leq m$ 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_i ( $∣ c ∣ = n$ |c|=n) — початкова кількість копійок у $i$ -тому місті;
$v_{i}$ v_i та $u_{i}$ u_i ( $∣ v ∣ = ∣ u ∣ = m$ |v|=|u|=m) — номери вершин, що з'єднує $i$ -та дорога;
$w_{i}$ w_i ( $∣ w ∣ = m$ |w|=m) — кількість копійок, необхідних на побудування $i$ -тої дороги;
ця функція повинна повертати true, якщо можливо правильно вибрати послідовність доріг, і false, якщо ні.

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

Вихідні дані

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

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

Приклади

Приклад 1

Приклад 2

Примітка

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

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

Оцінювання

( $3$ балів) $n \leq 10$ n \leq 10; $m = n - 1$ m = n - 1; $c_{i} = 1$ c_i = 1; $w_{i} = 1$ w_i = 1; якщо побудувати всі $m$ доріг, усі міста стануть сусідами;
( $8$ балів) $n, m \leq 10$ n,m \leq 10;
( $12$ балів) $n, m \leq 1 0^{5}$ n,m \leq 10^5; $c_{i} = 1$ c_i = 1;
( $14$ балів) $n, m \leq 1 0^{5}$ n,m \leq 10^5; усі $w_{i}$ w_i однакові;
( $16$ балів) $n, m \leq 1 0^{3}$ n,m \leq 10^3;
( $19$ балів) $n, m \leq 1 0^{5}$ n,m \leq 10^5;
( $12$ балів) $n, m \leq 5 \cdot 1 0^{5}$ n,m \leq 5 \cdot 10^5;
( $16$ балів) без додаткових обмежень.