Блог пользователя x1te

Система Непересекающихся Множеств
Автор x1te, 12 лет назад, По-русски

Всем привет! Я тут недавно решал тренировки и столкнулся с одной проблемой. Проблема возникла при написании(а написании ли?) СНМ в задаче D с вот этой тренировки. Старшие товарищи, если вы не против, можете, пожалуйста, сказать мне, как можно оптимизировать мой код, чтобы он не получал ТЛ.

Вроде бы глупых ошибок нет, да и все что мог, то соптимизировал. Заранее спасибо!

P.S. Извините за паскаль :]

UPD: Гигантское спасибо за советы, TL исправил. Сейчас буду бороться с WA =)
UPD2: Ура, сдал! Теперь баги с переполнениями нету, спасибо caustique за это.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Сжатия путей нет.

function findRoot(x: longint): longint;
begin
	if parent[x] <> parent[parent[x]] then 
		parent[x] := findRoot(parent[x]);
	result := parent[x];
end;
→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо, исправил. Но, почему-то, все равно TL 3.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Какая то странная у Вас функция объединения.
Если size равны, то к которому подвешиваем надо увеличить на 1. Иначе к большему подвесить меньшее.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Почитал на e-maxx. Там написано, что можно и так, как у меня.

    → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Можно хранить высоту, можно размер. Все оценки доказываются одинаково (ну O(log * ) точно, O(α) я доказывать не умею).

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Отправь под FPC. Известная проблема, что в Delphi int64 тормозит.

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

"извините за паскаль" made my day :)

→ Ответить