Memory limit exceeded на задаче по теории графов

@TheSuperSerg · Регистрация: 25.12.2018

Author24 — интернет-сервис помощи студентам

Пытался решить задачу №414 "Расследование" на acmp. Получил "Memory limit exceeded", хотя, как по мне, получил решение, которое должно работать.
Текст задачи:

В городском управлении милиции одного прибрежного города ведется расследование крупного дела, в котором могут быть замешаны сотрудники милиции. Было принято решение о тайной установке оборудования для просмотра информации, поступающей через Интернет. Под подозрение попадают два отдела, но добиться выделения денег на покупку двух комплектов оборудования не удалось. К счастью, внутренняя сеть управления имеет древовидную структуру, то есть каждый отдел имеет выход в Интернет через какой-либо другой отдел. Исключение составляет отдел по борьбе с компьютерными преступлениями, который имеет непосредственный доступ в Интернет по модемной линии.

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

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

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N (N ≤ 30000) – количество отделов. Во второй строке записаны номера двух отделов, за которыми необходимо установить слежение. На третьей строке находятся n-1 натуральных чисел, i-е из них не больше i и задает номер отдела, к которому подсоединен отдел i + 1.

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – номер отдела, в котором следует установить следящее оборудование.

Примеры
INPUT.TXT OUTPUT.TXT
1 ответ - 3
3 4
1 1 3

8
3 6
1 1 2 4 5 1 1 ответ - 1

Моё решение:

C++ (Qt)

#include <bits/stdc++.h>
#define lli unsigned short int
 
using namespace std;
 
lli o1,o2,v,e,m,s,mp;
 
int main()
{
    freopen("INPUT.TXT", "r", stdin);
    freopen("OUTPUT.TXT", "w", stdout);
    cin >> v;
    cin >> o1 >> o2;
    m=v+1;
    vector< vector<bool> > g(v, vector<bool>(v, 0));
    for(lli i = 0; i < v-1; i++)
    {
       cin >> e;
       if (e != 1)
       {
           g[e-1][i+1] = 1;
           for(lli j = 0; j < v; j++)
           {
               if (g[j][e-1] == 1) g[j][i+1] = 1;
           }
       }
       else
       {
           g[e-1][i+1] = 1;
       }
       g[i][i] = 1;
    }
    for(lli i = 0; i < v; i++)
    {
        s = 0;
        if (g[i][o1-1] == 1 && g[i][o2-1] == 1)
        {
            for(lli j = 0; j < v; j++)
            {
               s+=g[i][j];
            }
            if (m > s)
            {
                m = s;
                mp = i;
            }
        }
    }
    cout << mp+1 << endl;
    return 0;
}

Буду рад любой помощи.

@Apkawa · 14.10.2019, 09:26

Посмотрите ограничения задачи!
Ваш вектор для графа может содержать 30000^2 элементов

@TheSuperSerg · 14.10.2019, 14:28 **[ТС]**

Apkawa, как мне исправить эту проблему?

@VyacheslavSqrt · 23.07.2021, 22:36

Решение довольно понятное. Мы храним наше дерево как ориентированный граф, и за одно, чтобы не искать от куда идет наша вершина, в отдельном массиве храним ее предка. Запускаем дфс(можно и бфс) от минимального подозреваемого, если покрасили вторую вершину то минимальная это ответ, если нет то поднимаемся вверх и так в цикле. Асимптотика
О(n)

C++

#include <bits/stdc++.h>
using namespace std;
 
vector<int> g[30005];
vector<int> ret(30005);
vector<bool> used(30005);
int last, n; 
 
void dfs(int i) {
    used[i] = 1;
    for (auto& j : g[i]) {
        if (used[j] == 0) dfs(j);
    }
    return;
}
 
void solve(int i) {
    dfs(i);
    if (used[last]) { cout << i; return; }
    solve(ret[i]);
}
 
int main() {
    int first, tmp; cin >> n >> first >> last;
    if (last < first) swap(last, first);
    for (int i = 2; i <= n; i++) {
        cin >> tmp;
        g[tmp].push_back(i);
        ret[i] = tmp;
    }
    solve(first);
    return 0;
}

C++

Тест    Результат  Время  Память
1   Accepted    0,015   1112 Кб
2   Accepted    0,015   1108 Кб
3   Accepted    0,015   1108 Кб
4   Accepted    0,015   1116 Кб
5   Accepted    0,015   1108 Кб
6   Accepted    0,015   1112 Кб
7   Accepted    0,015   1112 Кб
8   Accepted    0,03    1112 Кб
9   Accepted    0,015   1112 Кб
10  Accepted    0,015   1108 Кб
11  Accepted    0,062   2336 Кб
12  Accepted    0,03    1224 Кб
13  Accepted    0,03    1280 Кб
14  Accepted    0,062   1404 Кб
15  Accepted    0,03    1392 Кб
16  Accepted    0,03    1332 Кб
17  Accepted    0,062   1408 Кб
18  Accepted    0,062   1372 Кб
19  Accepted    0,062   1424 Кб
20  Accepted    0,062   1408 Кб
21  Accepted    0,062   1460 Кб
22  Accepted    0,092   1468 Кб

@Kuzia domovenok · 23.07.2021, 23:29

VyacheslavSqrt, при чём тут это в теме про паскаль?
Автор давно покинул форум, вы его специально искали, чтобы решить ему давно ненужную задачу?

@VyacheslavSqrt · 24.07.2021, 11:53

Тоже задаюсь этим вопросом, я бы не стал писать, если человек, задающий вопрос, не прикрепил код на с++

@Kuzia domovenok · 24.07.2021, 18:52

VyacheslavSqrt, даже так, а смысл? Человек явно давно забил на вопрос.

@VyacheslavSqrt · 24.07.2021, 18:56

Опубликовать решение. Решений на эту задачу в публичном доступе небыло. Теперь некоторые люди могут просто скопипастить решение и заслать его.

@Apkawa 0 / 0 / 0 Регистрация: 19.08.2018 Сообщений: 1
	14.10.2019, 09:26	2
	Посмотрите ограничения задачи! Ваш вектор для графа может содержать 30000^2 элементов 0

@TheSuperSerg 0 / 0 / 0 Регистрация: 25.12.2018 Сообщений: 32
	14.10.2019, 14:28 [ТС]	3
	Apkawa, как мне исправить эту проблему? 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	23.07.2021, 23:29	5
	VyacheslavSqrt, при чём тут это в теме про паскаль? Автор давно покинул форум, вы его специально искали, чтобы решить ему давно ненужную задачу? 0

@VyacheslavSqrt 3 / 2 / 1 Регистрация: 29.10.2020 Сообщений: 28
	24.07.2021, 11:53	6
	Тоже задаюсь этим вопросом, я бы не стал писать, если человек, задающий вопрос, не прикрепил код на с++ 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	24.07.2021, 18:52	7
	VyacheslavSqrt, даже так, а смысл? Человек явно давно забил на вопрос. 0

@VyacheslavSqrt 3 / 2 / 1 Регистрация: 29.10.2020 Сообщений: 28
	24.07.2021, 18:56	8
	Опубликовать решение. Решений на эту задачу в публичном доступе небыло. Теперь некоторые люди могут просто скопипастить решение и заслать его. 0