Codeforces Round 895 (Div. 3) |
---|
Закончено |
Вы владелец зверинца, состоящего из $$$n$$$ животных пронумерованных от $$$1$$$ до $$$n$$$. Однако содержать зверинец достаточно затратно, поэтому вы решили его продать!
Известно, что каждое животное боится ровно одного другого животного. А точнее, животное $$$i$$$ боится животного $$$a_i$$$ ($$$a_i \neq i$$$). Также для каждого животного известна его стоимость, для животного $$$i$$$ она равняется $$$c_i$$$.
Вы будете продавать всех своих животных в каком-то зафиксированном порядке. Формально, вам надо будет выбрать некоторую перестановку$$$^\dagger$$$ $$$p_1, p_2, \ldots, p_n$$$, и продать сначала животное $$$p_1$$$, потом животное $$$p_2$$$, и так далее, последним продав животное $$$p_n$$$.
Когда вы продаёте животное $$$i$$$, есть два варианта развития событий:
Ваша задача — выбрать порядок продажи животных так, чтобы максимизировать суммарную прибыль.
Например, если $$$a = [3, 4, 4, 1, 3]$$$, $$$c = [3, 4, 5, 6, 7]$$$ и выбранная вами перестановка равна $$$[4, 2, 5, 1, 3]$$$, то:
Ваша суммарная прибыль при таком выборе перестановки, равна $$$12 + 4 + 14 + 6 + 5 = 41$$$. Обратите внимание, что $$$41$$$ — не максимально возможная прибыль в этом примере.
$$$^\dagger$$$ Перестановкой длины $$$n$$$ называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но в массиве присутствует $$$4$$$).
Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.
Далее следуют описания наборов входных данных.
Первая строка описания каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество животных.
Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$, $$$a_i \neq i$$$) — $$$a_i$$$ означает номер животного, которого боится животное $$$i$$$.
Третья строка набора входных данных содержит $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — стоимости животных.
Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$10^5$$$.
Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите $$$n$$$ целых чисел — перестановку $$$p_1, p_2, \ldots, p_n$$$, обозначающую, в каком порядке нужно продавать животных, чтобы максимизировать прибыль. Если есть несколько возможных ответов, можно вывести любой из них.
832 3 26 6 182 1 4 3 6 5 8 71 2 1 2 2 1 2 152 1 1 1 19 8 1 1 122 11000000000 99999999972 3 2 6 4 4 31 2 3 4 5 6 753 4 4 1 33 4 5 6 732 1 11 2 242 1 4 11 1 1 1
1 2 3 2 4 5 1 6 3 7 8 3 4 5 1 2 1 2 7 5 1 3 2 6 4 5 3 2 4 1 3 2 1 3 4 1 2
Название |
---|