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

Asan

Zaman limiti 5 saniyə-dir

Yaddaş məhdudiyyəti 1.024 meqabayt

Козак Вус нарешті знайшов країну своєї мрії. Вона складається з $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}$ копійок. Скажіть, чи можливо вибрати певну кількість доріг та впорядкувати їх так, щоб усі міста стали сусідами. А якщо це можливо, то знайдіть послідовність доріг, у якій їх потрібно будувати.

Giriş verilənləri

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

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

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

Qarşılıqlı təsir

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

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 для всіх побудованих доріг у тому порядку, у якому вони побудуються.

Çıxış verilənləri

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

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

Nümunələr

Giriş #1

Çıxış #1

Giriş #2

Çıxış #2

Qeyd

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

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

Qiymətləndirmə

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

Təqdimatlar 19

Qəbul dərəcəsi 5%