~~~~ program Project2;
const MaxN=100005; type TTree=array[1..MaxN] of Integer;
var N: Integer; // количество вершин Tree: TTree; //дерево x,y: Integer; //ребра дерева a,b,c: Integer; //начало, конец, узел проверки M: Integer; //количество тестов
function run(a,b,c: Integer): String; forward;
///инициализация procedure initial; begin N:=0; x:=0; y:=0; a:=0; b:=0; c:=0; M:=0; FillChar(Tree, SizeOf(Tree), 0); end;
///основная часть /// считывание /// обработка /// запись procedure readdata; var F: Text; i: Integer; G: Text; begin Assign(F, 'input.txt'); Reset(F); Assign(G, 'output.txt'); Rewrite(G); ReadLn(F,N); for i := 1 to N — 1 do begin ReadLn(F,x, y); if Tree[y]=0 then Tree[y]:=x else Tree[x]:=y; end; ReadLn(F, M); for i := 1 to M do begin ReadLn(F, a, b, c); WriteLn(G, run(a,b,c)); end; Close(G); Close(F); end;
function run(a,b,c: Integer): String; var i: Integer; begin run:='No'; for i := a to b do if (Tree[i]=c)Or(c=a)Or(c=b) then begin run:='Yes'; exit; end; end;
begin initial; readdata; end.
~~~~~
Проверка показала, что набрал из 10 балов 6. Я предполагаю не уложился по времени,тогда как нужно было изменить решение чтобы уложиться? Ведь если я буду использовать указатели, рекурсивный обход будет еще медленнее.
Как я понял, вы проверяли, ища путь. Я хочу предложить концептуально другое решение, которое легко уложиться во время. Давай будем просто проверять LCA. Можно даже попарно от всех трех, сути это не изменит. Потом проверим, совпадают ли они. Если да, то yes, иначе no. Плюс как я понял — это оффлайновая задача, а значит алгоритм Тарьяна ее решит очень эффективно.
P.S. Если написал бред, то извиняюсь, ибо не вчитывался и не вдумывался, но это первое, что пришло в голову.
P.P.S. Если нужны подробности, то отпишись
UPD. Все верно, я написал не бред :)
LCA проверять можно, но делать это надо аккуратно. То есть нужно проверить, что LCA(c,a)=LCA(b,a) AND LCA(c,b)=c или LCA(c,b)=LCA(b,a) AND LCA(c,a)=c. То есть, что c лежит или на ветке от a до общего предка выше a, или на ветке от b до общего предка выше b.
Я все-таки не совсем понимаю, почему нам недостаточно проверить LCA(a, b) = LCA(a, c) = LCA(b, c). Прошу привести пример, когда это выполнится, но при этом ответ будет неверным.
UPD. ЛАЖА
Тест: 1 2 1 3 1 4
Путь между 2, 4. 3 не принадлежит пути, но LCA совпадают
На самом деле это не выполняется почти никогда:).
Единственный случай, когда оно выполнится — это когда c и есть LCA(a,b). Так что всегда, когда это не так, одно из значений будет равно c, а два других — LCA(a,b).
Тест такой (шесть вершин):
1 2
2 3
3 4
1 5
5 6
Принадлежит ли 2 пути между 4 и 6?
UPD: Ответ на исходный вопрос — если все LCA равны, то ответ — "ДА". Но если не равны — то ответ не обязательно "НЕТ".
UPD2: Как было замечено выше, даже при равенстве LCA с может не лежать на пути. Так что всё ещё предлагаю свой вариант:).
Да, 2 принадлежит этому пути.
Я знаю. Но LCA(2,4)=2, а не 1, как остальные два LCA.
Действительно... Но выше я тоже нашел тест, который вылит такой подход. Сейчас подумаю, как бы все написать аккуратнее
UPD. Написанное вами выше должно работать нормально :) Спасибо за науку
Есть еще вариант: найти все lca: (a,b) (a,c) (b,c), через них посчитать расстояние. если получаем равенство расстояний (a,b) = (a,c)+(c,b) ответ yes, иначе no. ps: идея не моя.
Мой английский очень плох, вы не объясните,что за алгоритм LCA (код или для начала статью на русском (нашел только на английском)). Про алгоритм Тарьяна — здесь же обратные связи не дают другой маршрут. к тому же рекурсивный поиск разве не замедлит работу? и что значит оффлайновая задача?
LCA — это поиск наименьшего общего предка. Статься на емаксе есть. link. А сам алгоритм решает задачу за O(n + m). Что круто. Оффлайновая означает, что все запросы известны заранее и не происходит модификаций в дереве во время работы программы.
В коде также есть проблема со считыванием входных данных. Если попробовать такое дерево:
1 2
3 4
2 4
то можно увидеть, что при обработке третьей строки tree[2] и tree[4] будут уже заполнены. И тогда мы теряем или это ребро, или одно из предыдущих.
У меня просто возникали вопросы по считыванию: в примере почему-то указано 5 3, а мне казалось здесь ошибка и должно было быть 3 5. Но организатор ответил без комментарий
Тебе хотя бы ответили организаторы)
5 3 там так и должно быть, в условии же не указано, в каком порядке тебе что дано.
Ну я предполагал, что в начале дается родительский узел, а потом потомок
Ну, я этого не предполагал, получил 7 баллов. Возможно я сделал еще и лишнее предположение, что вершины сверху вниз пронумерованы, этого в условии тоже нет.
Что ты имеешь в виду? Приведи пж код как ты считывал. Просто я тогда не понимаю как можно определить, что есть родетелем, а что потомком
Эм, если принять то предположение, которое я озвучил выше как верное, то
Блин, но должен же был быть какой-то принцип считывания
Надо добавлять оба ребра, и в одну сторону, и в другую. Потом запустить dfs из первой вершины (будем считать ее корнем), тогда станет понятно, какая вершина есть предок какой.
P.S. используй
array[1..100000] of array of longintиsetlength, или самодельные связные списки (более трудный способ)На счет первой задачи. В голову приходит сразу написать выпуклую оболочку. А дальше что с ней сделать?...
Агоритм должен быть таким примерно (но я реализовать не успел. Чертов Пмм не мог что ли рекламки повесить про олимпиаду.) Результатом будет эллипс имеющий минимальную площадь.
1. Среди исходных точек находим три не лежащие на одной прямой. Если таких нет, то строим вырожденный ( с нулевой площадью ) эллипс и выходим из алгоритма. Иначе эти три точки считаем опорными и строим по ним эллипс. 2. Начало цикла. 3. Находим точку самую удалённую ( в специальной метрике ) от текущего эллипса. Если это расстояние равно нулю, то выходим из алгоритма. 4. Включаем эту точку в набор опорных точек. Для этого перебором строим новый элиипс для которого эта точка и старые опорные были бы внутри. К-во новых опорных точек будет не больше, чем пять — это к-во степеней свободы для эллипса. 5. Идём в начало цикла.
Как-то так)
Это наверное весьма умно цитировать без ссылки на источник? Не отсюда ли взято? :)
из выпуклой оболочки можно взять только конечные точки, а на остальные просто забить. Мне так показалось. Возможно ошибаюсь.
В тему соревнования по задаче 1: авторов задач с вещественным ответом и "ответ округлить до 5 знака после запятой" хочется немедленно отправлять работать на урановые рудники.
Ну на урановые рудники это как-то жестоко, но, имхо, в подобных задачах должен быть чекер, учитывающий возможную погрешность. Из формулировки с округлением напрашивается вывод, что задачу проверяли либо жестким сравнением вывода программы с выводом программы жюри, что не есть правильно, так как очевидно могут быть различные правильные ответы, либо не полностью — проверяли только площадь.