Submission #1245712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245712		Ice_man	Speedrun (RMI21_speedrun)	C++20	100 / 100	98 ms	47604 KiB

speedrun

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

using namespace std;

vector<long long>oiler;
vector<long long>graph[1'000'000];
vector<long long>tree[1'000'000];
bool vis[1'000'000];
long long par[1'000'000];

long long next1[1'000'000];

void dfs(long long x)
{

    vis[x]=true;
    if (oiler.size()!=0)
    {
        next1[oiler.back()]=x;
    }
    oiler.push_back(x);

    for (auto next:graph[x])
    {
        if (!vis[next]) dfs(next);
        par[next]=x;
    }
    return;
}


void assignHints(int subtask, int n, int a[], int b[])
{
    setHintLen(20);
    vector<pair<long long, long long>>v;
    for (long long i=1; i<n; i++)
    {
        v.push_back({a[i], b[i]});
        v.push_back({b[i], a[i]});
        graph[a[i]].push_back(b[i]);
        graph[b[i]].push_back(a[i]);
    }
    for (long long i=1; i<=n; i++) next1[i]=0;

    dfs(1);



    for (long long i=1; i<=n; i++)
    {
        long long x=par[i];
        for (long long j=1; j<=10; j++)
        {
            setHint(i, j, x%2);
            x/=2;
        }


        x=next1[i];
        for (long long j=11; j<=20; j++)
        {
            setHint(i, j, x%2);
            x/=2;
        }
    }
}



void speedrun(int subtask, int n, int start)
{
    long long root=start;

    while (root!=1)
    {
        long long p=0;

        for (long long j=1; j<=10; j++)
        {
            p+=(1<<(j-1))*getHint(j);
        }
        goTo(p);
        root=p;
    }



    while (true)
    {
        long long sled=0;
        for (long long j=11; j<=20; j++)
        {
            sled+=(1<<(j-11))*getHint(j);
        }


        if (sled==0)
        {
            break;
        }
        bool ret=goTo(sled);





        if (ret==0)
        {
            while (true)
            {
                long long pp=0;
                for (long long j=1; j<=10; j++)
                {
                    pp+=(1<<(j-1))*getHint(j);
                }
                goTo(pp);
                if (goTo(sled))
                {
                    break;
                }
            }
        }
    }

    return;
}

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