ПРОГРАММИРОВАНИЕ решить задачу на C++/Python
G. Браконьеры
ограничение по времени на тест: 1.5 секунд
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Алиса и Боб — два браконьера, которые рубят лес.
Лес это набор (возможно пустой) деревьев. Дерево — это связный граф без циклов. Подвешенное дерево имеет специальную вершину — корень. Родителем вершины v называется следующая вершина на кратчайшем пути от v до корня. Детьми вершины v называются вершины, для которых v является родителем. Вершина называется листом, если у неё нет детей.
В этой задаче мы определим глубину вершины как количество вершин на простом пути от этой вершины до корня. Рангом дерева назовем минимальную глубину его листа.
Изначально дан непустой лес подвешенных деревьев. Алиса и Боб играют в игру на этом лесе. Они ходят по очереди, Алиса ходит первой. В начале каждого хода игрок выбирает дерево из леса. Далее игрок выбирает положительное целое число — глубину разреза, которая не превосходит ранга выбранного дерева. Затем игрок удаляет из дерева все вершины, чьи глубины меньше либо равны глубине разреза. Все остальные вершины разбиваются на набор подвешенных деревьев, корнем каждого становится вершина, имевшая наименьшую глубину в дереве до разреза. Все эти деревья добавляются в лес и игра продолжается.
Игрок проигрывает, если на момент начала его хода лес пуст.
Определите, может ли Алиса победить, если оба игрока играют оптимально.
Входные данные
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число t (1≤t≤5⋅105) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка набора входных данных содержит одно целое число n (1≤n≤5⋅105) — суммарное количество вершин в деревьях изначального леса.
Вторая строка содержит n целых чисел p1,p2,…,pn (0≤pi≤n) — описание леса. Если pi=0, то i-я вершина дерева является корнем, иначе pi является родителем вершины i. Гарантируется, что p задает корректный лес подвешенных деревьев.
Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 5⋅105.
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если Алиса может победить, иначе выведите «NO» (без кавычек). Вы можете выводить каждую букву в любом регистре.
Пример
входные данные
4
4
0 1 0 3
7
0 1 2 0 4 5 6
4
0 1 1 2
7
0 1 1 2 2 3 3
выходные данные
NO
YES
NO
YES
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int x, y;
cin >> x >> y;
vector<vector<int> > t(x, vector<int> (y));
for (int i = 0; i < x; ++i){
for (int j = 0; j < y; ++j){
int mark;
cin >> mark;
t[i][j] = mark;
}
}
for (int i = 1; i < y; ++i){
t[0][i] += t[0][i - 1];
}
for (int i = 1; i < x; ++i){
t[i][0] += t[i - 1][0];
}
for (int i = 1; i < x; ++i){
for (int j = 1; j < y; ++j){
t[i][j] += min(t[i - 1][j], t[i][j - 1]);
}
}
cout << t[x - 1][y - 1] << endl;
}
Объяснение: