| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 829770 | raphaelp | Speedrun (RMI21_speedrun) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
void assign(int i, int N, int slot)
{
for (int j = 9; j >= 0; j--)
{
setHint(i, j + (10 * slot), N % 2);
N /= 2;
}
}
int rec(int p, int x, vector<bool> &occ, vector<vector<int>> &Tree, int last)
{
occ[x] = 1;
assign(p, x, 0);
if (Tree[x].size() == 1)
{
assign(x, last, 0);
}
for (int i = 0; i < Tree[x].size(); ++i)
{
if (occ[Tree[x][i]])
{
Tree[x].erase(i);
i--;
continue;
}
if (i != 0)
{
assign(Tree[x][i - 1], Tree[x][i], 1);
}
rec(x, Tree[x][i], occ, Tree, (i == Tree[x].size() - 1 || (i == Tree[x].size() - 2 && p == Tree[x][Tree[x].size() - 1])) ? last : x);
}
assign(Tree[x][Tree[x].size() - 1], x, 1);
}
void assignHints(int subtask, int N, int A[], int B[])
{
vector<vector<int>> Tree(N);
for (int i = 0; i < N - 1; i++)
{
Tree[A[i] - 1].push_back(B[i] - 1);
Tree[B[i] - 1].push_back(A[i] - 1);
}
setHintLen(20);
vector<bool> occ(N);
rec(0, 0, occ, Tree, 0);
}
int read(int slot)
{
int sum = 0;
for (int i = 0; i < 10; i++)
{
sum *= 2;
sum += getHint(i + (10 * slot));
}
return sum;
}
void speedrun(int subtask, int N, int start)
{
int x = start;
deque<int> pile;
vector<int> fils(N);
vector<int> bro(N);
vector<int> leaf(N);
vector<bool> failed(N, false);
vector<bool> failed2(N, false);
vector<bool> occ(N, 0);
int nbvis = 0;
bool depile = false;
while (nbvis < N)
{
if (!occ[x])
{
bro[x] = read(1);
fils[x] = read(0);
}
if (depile)
{
if (!occ[x])
nbvis++;
occ[x] = 1;
if (pile.size() > 1)
{
pile.pop_back();
leaf[pile.back()] = leaf[x];
bro[fils[pile.back()]] = bro[x];
x = pile.back();
depile = false;
}
else
{
pile.pop_back();
failed2[leaf[x]] = goTo(bro[leaf[x]]);
if (failed2[leaf[x]])
{
failed2[x] = goTo(bro[x]);
pile.push_back(bro[x]);
x = bro[x];
}
else
{
x = bro[leaf[x]];
pile.push_back(x);
depile = false;
}
}
}
else
{
if (pile.size() > 1 && fils[x] == pile[pile.size() - 2])
{
leaf[x] = x;
depile = true;
}
if (pile.front() == fils[x])
pile.pop_front();
if (occ[fils[x]])
{
failed2[fils[x]] = goTo(bro[fils[x]]);
if (!failed2[fils[x]])
{
x = bro[fils[x]];
continue;
}
depile = true;
}
else
{
failed[x] = goTo(fils[x]);
if (!failed[x])
{
pile.push_back(fils[x]);
x = fils[x];
continue;
}
}
}
}
}