% !TEX program = lualatex % (can also use "xelatex") 
\documentclass[12pt]{article}
\input{ejoi_structure.tex}

\usepackage[bulgarian]{babel}

\begin{document}

\renewcommand{\round}{Ден 1}
\renewcommand{\problemName}{Задача Тестове}
\renewcommand{\lang}{Български}

\renewcommand{\tl}{$0.8$ sec.}
\renewcommand{\ml}{$512$ MB}
\problem{\problemName}
В тази задача ще се опитаме да пресъздадем едно от предизвикателствата за авторите на задачи - генериране на тестове. Вашето предизвикателство е да генерирате дървета* и да отговаряте на заявки върху тях. Подробното описание е по-долу.\\\\
*Дърво - граф без цикъл. 
\subsection{Детайли по имплементацията}
Вие трябва да имплементирате следната функция:
\begin{lstlisting}
 std::vector<std::vector<std::pair<int,int>>> generate(int N, int T);
\end{lstlisting}
Тя ще бъде извикана веднъж от журито. Вие трябва да върнете $T$ различни дървета (като списък от ребра) с точно $N$ върха, в които коренът е 1. Ребрата в дърветата не трябва да имат тегло. Ако тези условия не са изпълнени, получавате грешен отговор на съответния тест. 
След това трябва да имплементирате следните три функции, с които ще отговаряте на заявки:
\begin{lstlisting}
 int query(int l, int r);
\end{lstlisting}
Тази функция може да бъде извикана многократно от журито. Вие трябва да върнете отговора на следния въпрос за Вашите генерирани дървета в миналата функция: \\
"В интервал от индекси \texttt{l} до \texttt{r} на дърветата, върнете височината* на дървото, което има най-голяма височина в този интервал."\\
*Височина на дърво - най-голямото разстояние от корена на дървото до някой връх. За разстояние приемаме бройката ребра, нужни за достигане на върха от корена.
\begin{lstlisting}
 void remove(int ind);
\end{lstlisting}
Тази функцията може да бъде извикана многократно от журито. Тя трябва да направи височината на дървото с индекс \texttt{ind} равна на 0 при отговаряне на заявките, т.е. съответното дърво не се брои. 
\begin{lstlisting}
 void add(int ind);
\end{lstlisting}
Тази функцията може да бъде извикана многократно от журито. Тя трябва да върне оригиналната височина на дървото с индекс \texttt{ind}.

\subsection{Ограничения}
Нека сумата от броя на всички извиквания на \texttt{query}, \texttt{remove} и \texttt{add} е равна на $Q$.
\begin{itemize}
\item $1 \leq N, T \leq 1067$
\item $0 \leq Q \leq 5*10^5$
\item $0 \leq l, r, ind \less T$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|}
\hline
\textbf{Подзадача} & \textbf{Точки} & \textbf{Ограничение}\\
\hline
$1$ & $6$ & $1 \leq N, T \leq $ около $6-7, Q = 0$\\
\hline
$2$ & $9$ & $1 \leq N, T \leq 34, Q = 0$\\
\hline
$3$ & $9$ & $1 \leq N, T \leq 167, Q = 0$\\
\hline
$4$ & $11$ & $1 \leq N, T \leq 1067, Q = 0$\\
\hline
$5$ & $4$ & $1 \leq N, T \leq $ около $6-7, Q = 1$\\
\hline
$6-7$ & $4$ & $1 \leq N, T \leq 34, Q = 1$\\
\hline
$6-7$ & $4$ & $1 \leq N, T \leq 167, Q = 1$\\
\hline
$8$ & $4$ & $1 \leq N, T \leq 1067, Q = 1$\\
\hline
$9$ & $9$ & $1 \leq N, T \leq 1067, 1 \leq Q \leq 5*10^5$, няма заявки \texttt{add}, \texttt{remove}\\
\hline
$10$ & $6$ & $1 \leq N, T \leq $ около $6-7, 1 \leq Q \leq 5*10^5$\\
\hline
$11$ & $7$ & $1 \leq N, T \leq 34, 1 \leq Q \leq 5*10^5$\\
\hline
$12$ & $3$ & $1 \leq N, T \leq 167, 1 \leq Q \leq 5*10^5$\\
\hline
$13$ & $24$ & $1 \leq N, T \leq 1067, 1 \leq Q \leq 5*10^5$\\
\hline
\end{tblr}
\end{table}
\FloatBarrier

\subsection{Пример}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|}
\hline
\textbf{Жури} & \textbf{Състезател}\\
\hline
\texttt{generate(4, 1)} & \texttt{\{\{\{1, 2\}, \{2, 3\}, \{3, 4\}\}\}}\\
\hline
\texttt{query(0, 0)} & 3\\
\hline
\texttt{remove(0)} & $ $\\
\hline
\texttt{query(0, 0)} & 0\\
\hline
\texttt{add(0)} & $ $\\
\hline
\texttt{query(0, 0)} & 3\\
\hline
\end{tblr}
\end{table}
\FloatBarrier

\subsection{Примерен грейдър}
Форматът на входа е следния:
\begin{itemize}
\item ред $1$: $N, T, Q$.
\item редове $2 - (Q+1)$: вид заявка (0 - \texttt{query}, 1 - \texttt{add}, 2 - \texttt{remove}) и аргументите й.
\end{itemize}
Грейдърът първо извежда върнатото от \texttt{generate}, а след това отговаря на всички заявки тип 0.

\end{document}


