Submission #643131

#	Time	Username	Problem	Language	Result	Execution time	Memory
643131		Tenis0206	Speedrun (RMI21_speedrun)	C++17	100 / 100	219 ms	940 KiB

speedrun

/**
* user:  arsenoiu-d07
* fname: Iulian George
* lname: Arsenoiu
* task:  Speedrun
* score: 100.0
* date:  2021-12-16 07:52:56.589066
*/
#include <bits/stdc++.h>
#include "speedrun.h"

using namespace std;

vector<int> G[1005];

int t[1005],l[1005];
int cnt = 0;


/// testing part

/*int hint[1005][1005];
int current_node = 0;

int ad[1005][1005];

int A[1005],B[1005];

void setHintLen(int val)
{
    return;
}

int getLength()
{
    int nu_a_intrebat_nimeni;
    return nu_a_intrebat_nimeni;
}

void setHint(int i, int j, int b)
{
    hint[i][j] = b;
}

int getHint(int j)
{
    return hint[current_node][j];
}

bool goTo(int nod)
{
    if(ad[current_node][nod])
    {
        current_node = nod;
        return true;
    }
    return false;
}
*/

///end of testing part

void dfs_set(int nod, int dad = 0)
{
    t[nod] = dad;
    l[++cnt] = nod;
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        dfs_set(it,nod);
    }
}

void set_dad(int nod, int dad)
{
    for(int j=0;j<10;j++)
    {
        setHint(nod,j+1,((dad&(1<<j))!=0));
    }
}

void set_next(int nod, int val)
{
    for(int j=0;j<10;j++)
    {
        setHint(nod,j+11,((val&(1<<j))!=0));
    }
}

void assignHints(int subtask, int n, int a[], int b[])
{
    for(int i=1;i<n;i++)
    {
        int x = a[i];
        int y = b[i];
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs_set(1);
    setHintLen(20);
    for(int i=1;i<=n;i++)
    {
        set_dad(i,t[i]);
    }
    for(int i=1;i<=n;i++)
    {
        set_next(l[i],l[i+1]);
    }
}

int get_dad()
{
    int dad = 0;
    for(int j=0;j<10;j++)
    {
        int b = getHint(j+1);
        if(b)
        {
            dad+=(1<<j);
        }
    }
    return dad;
}

int get_next()
{
    int u = 0;
    for(int j=0;j<10;j++)
    {
        int b = getHint(j+11);
        if(b)
        {
            u+=(1<<j);
        }
    }
    return u;
}

void speedrun(int subtask, int n, int start)
{
    int nod = start;
    getLength();
    while(nod!=1)
    {
        int t = get_dad();
        goTo(t);
        nod = t;
    }
    for(int i=1;i<n;i++)
    {
        int u = get_next();
        bool done = false;
        while(!done)
        {
            bool ok = goTo(u);
            if(ok)
            {
                break;
            }
            int t = get_dad();
            goTo(t);
        }
        //cerr<<current_node<<' ';
    }
}

/*int main()
{
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>A[i]>>B[i];
        ad[A[i]][B[i]] = ad[B[i]][A[i]] = true;
    }
    assignHints(0,n,A,B);
    int start;
    cin>>start;
    current_node = start;
    speedrun(0,n,start);
    return 0;
}
*/

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