Ускорить обход дерева

@CAXOPOK · Регистрация: 29.03.2013

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

Во входном файле ancestor.in в первой строке содержится количество узлов дерева, во второй строке массив чисел i-ое из которых определяет родителя вершины с номером i (0 - корень). В третьей строке число m - количество запросов, далее в m строках числа а и b(1<=a, b<=n).
Для каждого запроса в отдельную строку записать 1, если а является одним из предков b, иначе записать в строку 0.
пример входных данных
6
0 1 1 2 3 3
5
4 1
1 4
3 6
2 6
6 5
ответ
0
1
1
0
0
Вот что набросал:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<fstream>
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;
struct node
{
    int parent;
    set<int> children;
};
bool searcher(node* array, int a, int b)
{
    if( array[a].children.count(b)==1)
        return true;
    if(array[b].parent==0)
        return false;
            if(array[b].parent==a)
    {
     array[a].children.insert(b); 
     return true;
    }
    return searcher(array, a, array[b].parent);
}
 
int main()
{
    FILE *f;
    
    f=fopen("ancestor.in","r");
    int length;
    fscanf(f,"%d",&length);
    int tmp;
    node* array = new node[length+1];
    for(int i = 1; i <= length; ++i)
    {
        fscanf(f,"%d",&tmp);
        array[i].parent=tmp;    
        array[tmp].children.insert(i);
}   
    int numberOfRequests;
    fscanf(f,"%d",&numberOfRequests);
    int a,b;
 
    FILE *f2=fopen("ancestor.out","w");
    while(--numberOfRequests >= 0)
    {
        fscanf(f,"%d",&a);
        fscanf(f,"%d",&b);  
        if(searcher(array,a,b))
        {
            fprintf(f2,"1\n");
        }
        else
     fprintf(f2,"0\n");
 }  
    return 0;
}

Работает правильно, но медленно. Ошибка "Превышено отведённое время" (тест далеко не первый).
Пробовал ставить условие b>=a для ограничения перебора, но ошибки сразу в начальных тестах. Потому вопрос, как этот алгоритм можно ускорить?

@salam · 25.01.2015, 21:41

надо придумать другой алгоритм, который будет отвечать на запросы за $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathcal{O(1)}$ .

@CAXOPOK · 25.01.2015, 21:45 **[ТС]**

Отвечает за О(1), но снова не проходит по времени на том же тесте

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            System.IO.StreamReader file = new System.IO.StreamReader(@"ancestor.in");
            int Length = int.Parse(file.ReadLine());
            string[] arr = file.ReadLine().Split(' ');
            int[] array = new int[Length + 1];
            array[0] = -1;
 
            for (int i = 1; i <= Length;++i )
            {
                array[i] = int.Parse(arr[i - 1]);
            }
            List<int>[] Table = new List<int>[Length+1];
            for (int i=0; i<=Length;++i)
            {
              Table[i] = new List<int>();
            }
            
            int parent;
            for(int i = 1; i <=Length;++i)
            {
                parent = array[i];
                while(parent>0)
                {
                    Table[parent].Add(i);
                    parent = array[parent];
                }
            }
            int RequestNumber=int.Parse(file.ReadLine());
            int a, b;
            System.IO.StreamWriter sw = new System.IO.StreamWriter("ancestor.out");
            while(RequestNumber-->0)
            {
                arr = file.ReadLine().Split(' ');
                a = int.Parse(arr[0]);
                b = int.Parse(arr[1]);
                if(Table[a].Contains(b))
                {
                    sw.WriteLine("1");
                }
                else
                {
                    sw.WriteLine("0");
                }
            }
            sw.Close();
 
        }
    }
}

@SlavaSSU · 25.01.2015, 23:41

CAXOPOK, код, который заполняет массив table, работает за O(n^2). да и метод контейнс работает походу за O(n). И памяти массив table тоже жрет квадрат.

@CAXOPOK · 26.01.2015, 10:30 **[ТС]**

Памяти он занимает О(n*n) только в худшем случае, когда не дерево, а линия прямая. А contains за O(log n) работает

@SlavaSSU · 26.01.2015, 10:54

CAXOPOK, ну. квадрат времени и квадрат памяти.

@CAXOPOK · 26.01.2015, 20:18 **[ТС]**

Переделал под С++, время ответа на запрос О(1), но пошли ошибки исполнения.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<fstream>
#include<vector>
#include<iostream>
 
 
using namespace std;
class node
{
    public :
        vector<node*> children;
    int nasledniki;
        node()
    {
        nasledniki=0;
    }
    int number;
    int Numerate( int& num)
        {
            number = num;
            num++;
            nasledniki = children.size();
            if (children.size() > 0)
            {
                for(int i = 0; i < children.size();++i)
                {
                   nasledniki += children[i]->Numerate(num);
                } 
                
            }
            return nasledniki;
 
        }
};
 
int main()
{
 FILE *f;
   
    f=fopen("ancestor.in","r");
    int length;
    fscanf(f,"%d",&length);
    int tmp;
    node** nodeArr = new node*[length+1];
    int* array = new int(length+1);
    array[0]=0;
    nodeArr[0]=new node;
    for(int i = 1; i<=length;i++)
    {
        nodeArr[i]=new node;
        fscanf(f,"%d",&tmp);
        array[i]=tmp;
    }
    for(int i =1;i<=length;++i)
    {
        nodeArr[ array[i] ]->children.push_back(nodeArr[i]);
    }
    tmp=1;
    for(int i = 1; i<=length;i++)
    {
        if(array[i]==0)
        {
            
            nodeArr[i]->Numerate(tmp);
            break;
        }
    }
    
 
//  for(int i =1;i<=length;i++)
//  {
//      cout<<nodeArr[i]->number<< " ";
//  }
    int numberOfRequests;
    fscanf(f,"%d",&numberOfRequests);
    int a,b;
    FILE *f2=fopen("ancestor.out","w");
    while(--numberOfRequests >= 0)
    {
        fscanf(f,"%d",&a);
        
        fscanf(f,"%d",&b);  
        
        if(b>nodeArr[a]->number&&b<=nodeArr[a]->number+nodeArr[a]->nasledniki)
        {
            fprintf(f2,"1\n");
        }
        else
     fprintf(f2,"0\n");
    }  
    fclose(f2);
    fclose(f);
    return 0;
}

Добавлено через 37 минут
Есть этот же код и на шарпе

Добавлено через 4 часа 6 минут
Поясню, в памяти создаётся дерево (не бинарное) далее делаю его рекурсивный обход (корень, потомки по списку), и нумерую все узлы и запоминаю общее число потомков (не обязательно прямых). Это даёт возможность проверить родство узлов за время O(1). В массиве беру адрес нужны узлов и сравниваю. Значение в узле b должно быть больше значения в а но меньше либо равно значению в а + количество потомков а. На примере работает, но при тестировании системой выдаёт ошибку выполнения сразу на втором тесте.

Добавлено через 3 часа 28 минут
Подправил, но есть ошибки исполнения на уже других тестах

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<fstream>
 
#include<vector>
#include<iostream>
 
 
using namespace std;
class node
{
    public :vector<node*> children;
    int nasledniki;
    node()
    {
        nasledniki=0;  
    }
    int number;
    int Numerate( int& num)
        {
            number = num;
            num++;
            nasledniki = children.size();
            if (children.size() > 0)
            {
                for(int i = 0; i < children.size();++i)
                {
                   nasledniki += children[i]->Numerate(num);
                } 
                
            }
            return nasledniki;
 
        }
};
 
int main()
{
 FILE *f;
   
    f=fopen("ancestor.in","r");
    int length;
    fscanf(f,"%d",&length);
    int tmp;
    node** nodeArr = new node*[length+1];
    int* array = new int(length+1);
    array[0]=0;
    nodeArr[0]=new node;
    for(int i = 1; i<=length;i++)
    {
        nodeArr[i]=new node;
        fscanf(f,"%d",&tmp);
        array[i]=tmp;
    }
    for(int i =1;i<=length;++i)
    {
        nodeArr[ array[i] ]->children.push_back(nodeArr[i]);
    }
    tmp=1;
    for(int i = 1; i<=length;i++)
    {
        if(array[i]==0)
        { 
            nodeArr[i]->Numerate(tmp);
        }
    }
 
    int numberOfRequests;
    fscanf(f,"%d",&numberOfRequests);
    int a,b;
    FILE *f2=fopen("ancestor.out","w");
    while(--numberOfRequests >= 0)
    {
        fscanf(f,"%d",&a);
        fscanf(f,"%d",&b);
          
        if(a>length || b>length || a<1||b<1)
        {
            fprintf(f2,"0\n");
            continue;
        }
        if( nodeArr[b]->number>nodeArr[a]->number  &&  nodeArr[b]->number<=nodeArr[a]->number+nodeArr[a]->nasledniki)
        {
            fprintf(f2,"1\n");
        }
        else
        fprintf(f2,"0\n");
    }  
    fclose(f2);
    fclose(f);
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	25.01.2015, 21:41
	надо придумать другой алгоритм, который будет отвечать на запросы за $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathcal{O(1)}$ . 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	25.01.2015, 23:41
	CAXOPOK, код, который заполняет массив table, работает за O(n^2). да и метод контейнс работает походу за O(n). И памяти массив table тоже жрет квадрат. 0

@CAXOPOK 2 / 2 / 0 Регистрация: 29.03.2013 Сообщений: 59
	26.01.2015, 10:30 [ТС]
	Памяти он занимает О(n*n) только в худшем случае, когда не дерево, а линия прямая. А contains за O(log n) работает 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	26.01.2015, 10:54
	CAXOPOK, ну. квадрат времени и квадрат памяти. 0