Submission #1118842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118842		MateiKing80	Speedrun (RMI21_speedrun)	C++14	100 / 100	236 ms	2184 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

/*
void setHintLen (int l);
void setHint(int i, int j, bool b);
int getLength ();
bool getHint(int j);
bool goTo(int x);

intr-un nod ne tinem 2 lucruri: cel mai din stanga fiu si urmatorul fiu mai la dreapta
al tatalui nodului
*/

vector<int> vec[1005];
vector<int> fii[1005];


void bagaHint(int nod, int val)
{
    for(int i = 1; i <= 20; i ++)
        if(val & (1 << (i - 1)))
            setHint(nod, i, 1);
}

void dfsHint(int nod, int papa, int fiuDrPapa)
{
    for(auto i : vec[nod])
    {
        if(i == papa)
            continue;
        fii[nod].push_back(i);
    }
    bagaHint(nod, fiuDrPapa);
    if(fii[nod].empty())
        return;
    bagaHint(nod, (1 << 10) * fii[nod][0]);
    int fprec = papa;
    for(int i = fii[nod].size() - 1; i >= 0; i --)
    {
        dfsHint(fii[nod][i], nod, fprec);
        fprec = fii[nod][i];
    }
}

void assignHints(int subtask, int n, int A[], int B[])
{
    setHintLen(20);
    for(int i = 1; i < n; i ++)
        vec[A[i]].push_back(B[i]),
        vec[B[i]].push_back(A[i]);
    dfsHint(1, 0, 0);
}

int nextdr()
{
    int ans = 0;
    for(int i = 1; i <= 10; i ++)
        if(getHint(i))
            ans += (1 << (i - 1));
    return ans;
}

int fiust()
{
    int ans = 0;
    for(int i = 1; i <= 10; i ++)
        if(getHint(i + 10))
            ans += (1 << (i - 1));
    return ans;
}


void dfs(int nod, int papa)
{
    if(fiust() == 0)
        return;
    auto x = fiust();
    while(x != papa)
    {
        goTo(x);
        dfs(x, nod);
        x = nextdr();
        goTo(nod);
        if(x != papa)
            goTo(x);
    }
}

void speedrun(int subtask, int n, int start)
{
    if(n == 1)
        return;
    int nod = start;
    while(1)
    {
        int x = fiust();
        if(x == 0)
            break;
        goTo(x);
        nod = x;
    }
    int papa = -1;
    for(int i = 1; i <= n; i ++)
        if(i != nod && goTo(i))
        {
            papa = i;
            break;
        }
    goTo(nod);
    while(nod != 1)
    {
        int nxt = nextdr();
        goTo(papa);
        if(papa == 1)
            break;
        if(nxt == 0 || !goTo(nxt))
            swap(nod, papa);
        else
            nod = nxt;
    }
    dfs(1, 0);
}

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40