\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	
\renewcommand{\tl}{$3$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача GT24. ПУМА}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 5 май 2026 г.\\
	Група G
}

\begin{wrapfigure}{r}{0.37\textwidth}
	\begin{adjustbox}{width=0.37\textwidth}
		\includegraphics{puma.png}
	\end{adjustbox}
\end{wrapfigure}
Дива черна пума е била забелязана в природен парк Шуменско плато близо до град Шумен. Общината е извикала $K$ зоолози, за да заловят животното.

За опростяване ще считаме, че паркът има $N$ главни места, означени (физически) с целите числа от $0$ до $N-1$. Тези места са свързани с $N-1$ двупосочни пътеки, така че е възможно да се достигне до всяко място от всяко друго чрез тези пътеки. Ще наричаме две места пряко свързани с пътека \textit{съседни}.

Правителството иска всяко място да бъде изследвано от поне един зоолог. Всеки зоолог ще започне от началната точка на парка, която е място номер $0$, и ще се движи по пътеките \textbf{без} да посещава отново места, които вече е изследвал. Те ще напускат парка, когато няма повече места, до които могат да отидат (без да се връщат). Ще наричаме такива места (където трябва да се напусне парка при пристигане) \textit{изходи}.

Поради съображения за безопасност, само един зоолог може да бъде в парка в даден момент. Има конкуренцията между зоолозите и затова те са решили, че единствената „комуникация“{} между тях ще бъде маркиране на местата с цели числа от $0$ до $M$ включително. Първоначално всички маркировки са $0$.

Зоолозите ще влизат и излизат един след друг, в ред, който не е известен предварително. Тъй като някой е откраднал картата на парка, когато един зоолог е на дадено място, той:
\begin{itemize}
	\item знае откъде е дошъл;
	\item знае номера и маркировката на текущото място;
	\item вижда маркировките на всички \textit{съседни} места, но \textbf{не} и техните номера.
\end{itemize}

Помогнете на зоолозите да измислят стратегия, така че всяко място да бъде изследвано от поне един зоолог. Знаете също, че $K$ е точно равно на броя на \textit{изходите} и че $M$ е достатъчно, за да има валидна стратегия.

\subsection{Детайли по имплементацията}
Стратегията трябва да бъде имплементирана чрез следната функция:
\begin{lstlisting}
 void zoologist (int N, int K, int M, std::vector<int> p, int m, std::vector<int> a)
\end{lstlisting}
\begin{itemize}
	\item $N$: броят на местата в парка;
	\item $K$: броят на зоолозите;
	\item $M$: максималната стойност на маркировката;
	\item $p$: вектор с дължина $N$, представящ пътеките; за $1 \le i \le N-1$ има пътека между място $p[i]$ и $i$, и $p[0] = -1$;
	\item $m$: текущата маркировка на началното място $0$;
	\item $a$: вектор, представящ маркировките на всички \textit{съседни} места на $0$, \textbf{в произволен ред}.
\end{itemize}
Тази функция ще бъде извикана $K$ пъти -- по веднъж за всеки от зоолозите. Извикванията ще бъдат последователни, т.е. когато първият зоолог приключи своето изследване, ще бъде направено извикване за втория зоолог с текущото състояние на маркировките и т.н. Тези извиквания могат да бъдат в \textbf{отделни изпълнения} за различните зоолози, но някои извиквания може да са в едно и също изпълнение. По този начин се симулира, че единствената комуникация между зоолозите ще бъде чрез маркировките. Следователно вашата програма \textbf{не трябва} да се опитва да използва глобална памет между различните извиквания.

Горната функция може да извиква следните функции, за да промени маркировката на текущото място или да се премести до \textit{съседно} място:
\begin{lstlisting}
 void set_marking (int m)
\end{lstlisting}
\begin{itemize}
	\item $m$: стойността на новата маркировка за текущото място, която трябва да бъде цяло число между $0$ и $M$ включително.
\end{itemize}
\begin{lstlisting}
 std::pair<int, std::vector<int>> movement (int i)
\end{lstlisting}
\begin{itemize}
	\item $i$: индекс на пътеката, по която да се премине, спрямо вектора от маркировки на \textit{съседните} места (в началото това е векторът $a$, а след това вторият елемент от последната върната стойност от функцията \texttt{movement});
	\item тази функция връща две стойности -- първата е номерът на следващото място, а втората е вектор, представящ маркировките на всички места, \textit{съседни} на следващото място (без маркировката на мястото, от което е дошъл зоологът), \textbf{в произволен ред}.
\end{itemize}

Ако зоологът се намира на \textit{изход}, просто прекратете функцията, за да симулирате напускане на парка.

\subsection{Ограничения}
\begin{itemize}
	\item $1 \leq N \leq 1000$
	\item $K$ е равно на броя на \textit{изходите}.
	\item Съществува валидна стратегия за даденото $M$.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{\makecell{Необходими\\подзадачи}} & $M$ & \textbf{Други ограничения}\\
		\hline
		$0$ & $0$ & $-$ & $-$ & Примерът. \\
		\hline
		$1$ & $6$ & $-$ & $=1$ & Място $0$ е пряко свързано с всички останали места. \\ 
		\hline
		$2$ & $14$ & $-$ & $=N$ & -- \\ 
		\hline
		$3$ & $15$ & $0$ & \SetCell[r=3]{m}{$=C^*$} & $N = 2^s-1$, място $0$ има две \textit{съседни} места, $2^{s-1}-2$ от местата имат по три \textit{съседни} места, а останалите имат само по едно \textit{съседно} място. \\ 
		\hline
		$4$ & $18$ & $0, 3$ & & Във вектора $p$ няма уникални стойности освен $-1$. \\
		\hline 
		$5$ & $47$ & $0 - 4$ & & -- \\
		\hline
	\end{tblr}
	\caption*{$^*$ $C$ е максималният брой пътеки, които един зоолог може да премине, започвайки от място $0$.}
\end{table}
\FloatBarrier

\newpage
\subsection{Пример}
Нека разгледаме следната схема на местата и пътеките в парка:

\begin{adjustbox}{center}
	\includesvg[inkscapelatex=false]{graph}
\end{adjustbox}

Следните таблици показват примерна последователност от движения и маркировки за $M=4$:
\begin{table}[H]
	\begin{tblr}{|c|X[c]|}
		\hline
		\textbf{\makecell{Вашите действия}} & \textbf{Действия на грейдъра} \\
		\hline
		& \texttt{zoologist(7,4,4,\{-1, 0, 0, 1, 1, 2, 2\},0,\{0, 0\})} \\
		\hline
		\texttt{set\_marking(1)} & \\
		\hline
		\texttt{movement(0)} & \texttt{return \{1, \{0, 0\}\}} \\
		\hline
		\texttt{movement(1)} & \texttt{return \{4, \{\}\}} \\
		\hline
		\texttt{set\_marking(2)} & \\
		\hline
	\end{tblr}
\end{table}

\begin{table}[H]
	\begin{tblr}{|c|X[c]|}
		\hline
		\textbf{\makecell{Вашите действия}} & \textbf{Действия на грейдъра} \\
		\hline
		& \texttt{zoologist(7,4,4,\{-1, 0, 0, 1, 1, 2, 2\},1,\{0, 0\})} \\
		\hline
		\texttt{set\_marking(2)} & \\
		\hline
		\texttt{movement(0)} & \texttt{return \{2, \{0, 0\}\}} \\
		\hline
		\texttt{set\_marking(1)} & \\
		\hline
		\texttt{movement(1)} & \texttt{return \{6, \{\}\}} \\
		\hline
		\texttt{set\_marking(1)} & \\
		\hline
		
		& \texttt{zoologist(7,4,4,\{-1, 0, 0, 1, 1, 2, 2\},2,\{1, 0\})} \\
		\hline
		\texttt{set\_marking(3)} & \\
		\hline
		\texttt{movement(1)} & \texttt{return \{1, \{2, 0\}\}} \\
		\hline
		\texttt{set\_marking(0)} & \\
		\hline
		\texttt{movement(1)} & \texttt{return \{3, \{\}\}} \\
		\hline
		
		& \texttt{zoologist(7,4,4,\{-1, 0, 0, 1, 1, 2, 2\},3,\{0, 1\})} \\
		\hline
		\texttt{set\_marking(4)} & \\
		\hline
		\texttt{movement(1)} & \texttt{return \{2, \{0, 1\}\}} \\
		\hline
		\texttt{movement(0)} & \texttt{return \{5, \{\}\}}\\
		\hline
		\texttt{set\_marking(1)} & \\
		\hline
	\end{tblr}
\end{table}

\subsection{Локален грейдър}
За локалния грейдър всички $K$ извиквания на \texttt{zoologist} са в рамките на едно и също изпълнение.

Формат на входа:
\begin{itemize}
	\item ред $1$: три цели числа -- стойностите на $N$, $K$ и $M$;
	\item ред $2$: $N$ цели числа -- стойностите на вектора $p$.
\end{itemize}

Формат на изхода:
\begin{itemize}
	\item ред $1$: $N$ булеви стойности -- $1$, ако съответното място е изследвано от поне един зоолог, и $0$ в противен случай.
\end{itemize}

За по-подробна информация променете стойността на макроса \texttt{DETAILED} от \texttt{false} на \texttt{true} в първия ред на локалния грейдър.
	
\end{document}