На последнем контесте была задача D. Кай и снежинки. В разборе написано, что вполне подойдет решение в каждой вершине сливать сеты ее потомков.

Очевидно, что худший тест — это просто цепь из 300000 вершин. Тогда получается, что в каждой вершине будет 1, 2, 3,..., 300000 элементов в сете. Всего элементов (арифм. прогрессия) 300000 * 300000 / 2 ~= 45 * 10^9.

Это катастрофически много. Когда я попытался именно сохранить все эти сеты, то, разумеется, получил ML. Однако, если написать как в разборе, то есть просто запуститься рекурсивно из корня и постепенно получать ответ для него (не сохраняя сами сеты), то получим Accepted.

Так вот по сути же выделяем под те же 45 * 10^9 интов. Единственное, что приходит в голову, то что сет после выполнения функции чистит за собой память, которую потребовал в ходе выполнения этой функции, и в последствии может снова использовать ее же.

1) Подскажите, это правда так?

Грубо говоря, есть цикл for (int i = 0; i < 100000; i++) { set a; a.insert(3); }

Правда ли, что потребуется памяти столько, сколько необходимо на одну итерацию? Я просто раньше думал, что выделяется всегда абсолютно новая область памяти. Помогите разобраться, пожалуйста.