1 Отредактировано zodiac (2011-12-08 00:04:50)

Тема: Декартово дерево

Добрый день!
Не могу понять почему данное решение проходит в контесте 20 тестов и дальше валится с неправильным ответом. Код переделывал на си с этого сайта, почти точь-в-точь.

Мое решение

Условие задачи. Задана последовательность команд (каждая в отдельной строке), которые необходимо выполнить.
A key data - добавляет элемент в дерево с ключом key и данными data (если элемент существует, то просто перезаписать поле data),
D key, S key - удаляет и ищет соответственно.
F - освобождает память, занимаемую деревом. Всегда идет в конце.

key, data - 32-битные целые числа.

Примеры:
Вход:
A 10 20
A 20 30
S 10
D 20
S 20
F
Выход:
10 20

Вход:
A 20 30
S 20
A 20 50
D 10
S 20
F
Выход:
20 30
20 50

2

Re: Декартово дерево

В код не вчитывался, но мне кажется, что неправильно работать может то, когда вы вызываете insert() от ключа, уже имеющегося в дереве (не проверяя, что такого ключа не было). Скажем, если node->prior получился большим, чем у всех вершин дерева, то эта новая вершина встанет в корень, а остальное дерево просто просплитится на два - и в результате могут появиться две вершины с одинаковым key.

3

Re: Декартово дерево

Я тоже сначала так подумал, но тогда я добавил перед добавлением элемента его удаление, но все равно неправильный ответ на том же тесте.

4

Re: Декартово дерево

Если так вы уже пробовали - тогда не знаю. Просмотром кода я ничего тут не увидел.

В таких случаях, когда ошибку долго не получается найти, разумнее всего сделать стресс-тест: написать простое решение за квадрат и запускать оба решения много раз на случайных тестах.

5

Re: Декартово дерево

То есть код правильный? Хм... Спасибо, буду искать %)

6 Отредактировано zodiac (2011-12-09 23:59:21)

Re: Декартово дерево

Ошибку нашел. Она была связана с тем, что указатель root в main() был ненулевым, а также необходимо было удалять элемент перед добавлением ( как Вы писали выше ).

Спасибо!