Submission #833397

#	Time	Username	Problem	Language	Result	Execution time	Memory
833397		RaulAndrei01	Speedrun (RMI21_speedrun)	C++17	100 / 100	174 ms	852 KiB

speedrun

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

using namespace std;
const int NMAX = 1001;
vector<int> adj[NMAX];
stack<int> ord;

void setPar (int nod , int par)
{
    int bit = 1;
    while (par)
    {
        setHint(nod , bit , par&1);
        bit++;
        par /= 2;
    }
}

void setNext (int nod , int nxt)
{
    int bit = 11;
    while (nxt)
    {
        setHint(nod , bit , nxt&1);
        bit++;
        nxt /= 2;
    }
}

void dfs (int nod = 1 , int par = 0)
{
    ord.push(nod);
    for (auto& to : adj[nod])
    {
        if (to == par) continue;
        setPar(to , nod);
        dfs(to , nod);
    }
}

void assignHints(int subtask, int N, int A[], int B[])
{
    setHintLen(20);
    for (int i = 1; i < N; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    dfs();
    int prev = 1;
    while (ord.size())
    {
        setNext(ord.top() , prev);
        prev = ord.top();
        ord.pop();
    }
}

int getPar (int nod)
{
    int par = 0;
    for (int bit = 10; bit > 0; bit--)
    {
        
        par = (par << 1) + getHint(bit);
    }

    return par;
}

int getNext (int nod)
{
    int nxt = 0;
    for (int bit = 20; bit > 10; bit--)
    {
        nxt = (nxt << 1) + getHint(bit);
    }
    return nxt;
}

void speedrun(int subtask, int N, int start)
{
    vector<bool> viz(N+1, 0);
    int visited = 1;
    int crt = start;
    viz[crt] = 1;
    while (visited < N)
    {
        int nxt = getNext(crt);
        while (goTo(nxt) == 0)
        {
            int par = getPar(crt);
            goTo(par);
            crt = par;
        }
        crt = nxt;
        visited++;
        viz[crt] = 1;
    }

}

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