#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> dwnl;
vector<int> nxtl;
void dfs(int x, int p, int nxt)
{
nxtl[x] = nxt;
int nnxt = p;
for (int ch : adj[x])
{
if (ch != p)
{
dfs(ch, x, nnxt);
nnxt = ch;
}
}
dwnl[x] = nnxt;
}
void assignHints(int subtask, int N, int A[], int B[])
{ /* your solution here */
adj = vector<vector<int>>(N + 1);
nxtl = vector<int>(N + 1);
dwnl = vector<int>(N + 1);
setHintLen(20);
for (int i = 1; i < N; i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1, 0, 0);
for (int i = 1; i <= N; i++)
{
// cout << "\n"
// << i << " "
// << dwnl[i] << " " << nxtl[i] << "\n";
for (int j = 0; j < 10; j++)
{
setHint(i, j + 1, (dwnl[i] & (1 << j)) > 0);
}
for (int j = 10; j < 20; j++)
{
setHint(i, j + 1, (nxtl[i] & (1 << (j - 10))) > 0);
}
}
}
vector<int> getValue()
{
vector<int> ret(2, 0);
for (int j = 0; j < 10; j++)
{
ret[0] = ret[0] | (getHint(j + 1) << j);
}
for (int j = 10; j < 20; j++)
{
ret[1] = ret[1] | (getHint(j + 1) << (j - 10));
}
return ret;
}
void speedrun(int subtask, int N, int start)
{
nxtl = vector<int>(N + 1, -1);
dwnl = vector<int>(N + 1, -1);
int x = start;
int prev = 0;
int viz = 0;
while (viz < N)
{
if (dwnl[x] == -1)
{
viz++;
vector<int> data = getValue();
dwnl[x] = data[0];
nxtl[x] = data[1];
}
// cout << "\n"
// << x << " "
// << dwnl[x] << " " << nxtl[x] << "\n";
dwnl[prev] = nxtl[x];
bool go = goTo(dwnl[x]);
if (go)
{
prev = x;
x = dwnl[x];
}
else
{
x = prev;
goTo(prev);
prev = 0;
};
}
}
