|
|
|
|
|
|
|
Вернуться
| 1 Георгий Шарушинский, 27 ноября 2018 г. 19:05:19 | |
На с++ у меня на всех задачах не больше 5 мб
|
|
|
| 2 Меньшиков Фёдор Владимирович, 05 ноября 2018 г. 15:08:33 | |
|
Ограничение памяти в этой задаче подняли до 32 Мбайт, вариант с ArrayList<Integer> теперь проходит.
|
|
|
| 3 Меньшиков Фёдор Владимирович, 05 ноября 2018 г. 13:24:42 | |
|
С таким подходом к спискам смежности сдал с расходом памяти 6.4 Мбайт. Правда, в предыдущем сообщении баг в коде - первое ребро графа игнорируется. Правильно вот так (nV число вершин, nE число рёбер): инициализация int first[] = new int[1 + nV]; int vertex[] = new int[1 + nE]; int next[] = new int[1 + nE]; int size = 1; добавление ребра v1->v2: vertex[size] = v2; next[size] = first[v1]; first[v1] = size; size++; проход по рёбрам вершины v: for (int i = first[v]; i != 0; i = next[i]) { int child = vertex[i]; ... }
|
|
|
| 4 Меньшиков Фёдор Владимирович, 05 ноября 2018 г. 13:06:44 | |
|
Богдан, также Вы можете использовать подход классического Паскаля для реализации списков смежности (как я понимаю, основная загвоздка по памяти в них). Инициализация int first[] = new int[1 + nV]; int vertex[] = new int[nE]; int next[] = new int[nE]; int unused = 0; Добавление ребра v1->v2: vertex[unused] = v2; next[unused] = first[v1]; first[v1] = unused; unused++; Проход по рёбрам вершины v1: for (int v = first[v1]; v != 0; v = next[v]).
|
|
|
| 5 Меньшиков Фёдор Владимирович, 05 ноября 2018 г. 12:53:50 | |
|
Сейчас написал свой IntArrayList - простейший на 22 строчки - с методами add, get, size - и прошло с памятью 9.9 Мбайт.
|
|
|
| 6 Яндулов Богдан, 05 ноября 2018 г. 10:45:35 | |
|
Почему бы вообще не поднять ML для всех задач? На тимусе стандартный ML 64 Мб, на CF вообще 256.
|
|
|
| 7 Яндулов Богдан, 05 ноября 2018 г. 10:43:44 | |
|
По идее, обычный Косарайю, где 2 массива списков, должен заходить без проблем. Но ML 8. С одним массивом списков - ML14.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
