Memory limit exceeded на задаче по теории графов - Pascal ABC - Ответ 13828173

@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;
}

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

Вернуться к обсуждению:
Memory limit exceeded на задаче по теории графов Pascal ABC

Следующий ответ

Другие темы раздела
Pascal ABC Разработать программу для определения взаимного расположения(пересечение,касание,концентричность,вложенность)двух фигур https://www.cyberforum.ru/ pascalabc/ thread2500047.html Круг и равнобедренный треугольник	Pascal ABC Сортировка массива "пузырьком" по возрастанию Напишите алгоритм пожалуйста
Pascal ABC Определение взаимного расположения (пересечение, касание, концентричность, вложенность) двух заданных фигур https://www.cyberforum.ru/ pascalabc/ thread2499485.html Разработать программу для определения взаимного расположения (пересечение, касание, концентричность, вложенность) двух заданных фигур:Полуэллипс и прямоугольный треугольник хотелось бы получить код по данной работе	Pascal ABC Какую можно программу для дипломной работы написать? Привет. Какую можно программу для дипломной работы написать? Желательно, чтобы потом и экзешник был. https://www.cyberforum.ru/ pascalabc/ thread2499038.html
Вычислить значения сумм ряда Pascal ABC смотрите вложения!!	Pascal ABC Составить программу, которая по первой букве профессии или номеру в списке распечатает профессию и заработную плату https://www.cyberforum.ru/ pascalabc/ thread2498609.html Дан список профессий и заработная плата на этой профессии: столяр - 2000 р., сварщик - 3000 р., шофер - 2500 р., бухгалтер - 3500 р. Составить программу, которая по первой букве профессии или номеру в списке распечатает профессию и заработную плату этой профессии, иначе такой профессии нет.
Pascal ABC Найти такое c, что a<c<b и b делится на c, а c делится на а https://www.cyberforum.ru/ pascalabc/ thread2497911.html Заданы числа a и b, требуется найти такое c что a<c<b и b делится на c, а c делиться на а, если такого числа не существует вывести -1	Изобразить на экране изменение изображения домов при движении наблюдателя вдоль улицы Pascal ABC На горизонтальной плоскости расположены 4 параллелепипеда, являющиеся условным изображением 4 домов одной улицы (по 2 дома на каждой стороне). Изобразить на экране изменение изображения "домов" при движении наблюдателя вдоль "улицы". (Использовать центральную проекцию). Подскажите, как сделать, буду очень благодарна
Pascal ABC Вычислить сумму ряда. Даны натуральное число n и действительно число x . Нужно вычислить S= sinX+sinX+...+ {sinXsinX+...*sinX} n раз Срочно помогите, пожалуйста https://www.cyberforum.ru/ pascalabc/ thread2497252.html	Pascal ABC Футбольный турнир. https://www.cyberforum.ru/ pascalabc/ thread2496573.html Количество мячей, забитых и пропущенных футбольной командой в каждом из 22 игр, записано в массиве, элементами которого являются величины типа 'запись' а) для каждой проверенной игры напечатать словесный результат :" выигрыш", "ничья", "проигрыш ". б) определить количество выигрышей данной команды. в) определить количество выигрышей и количество проигрышей данной команды Г) определить...
Pascal ABC Строка: Определить и напечатать те буквы второго предложение, из которых состоит первое. Вводится два предложения. Определить и напечатать те буквы второго предложение, из которых состоит первое.	Pascal ABC Вывод простых делителей числа,ошибка program abcd; var i,a,k,n,ia,S,j:integer; begin readln(k); n:=k-1; writeln(k,'='); for i:=1 to n do begin if k mod i =0 then S:=i; for j:=1 to S do begin https://www.cyberforum.ru/ pascalabc/ thread2496292.html

	14.09.2019, 21:29