Submission #649078

#	Time	Username	Problem	Language	Result	Execution time	Memory
649078		boris_mihov	Speedrun (RMI21_speedrun)	C++17	100 / 100	227 ms	840 KiB

speedrun

#include "speedrun.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 1000 + 10;
const int INF  = 1e9;

int n;
int parent[MAXN];
int nextInTour[MAXN];
std::vector <int> tour;
std::vector <int> g[MAXN];

void dfs(int node, int p)
{
    parent[node] = p;
    tour.push_back(node);
    for (const int &i : g[node])
    {
        if (i == p) continue;
        dfs(i, node);
    }
}

void assignHints(int subtask, int N, int A[], int B[])
{
    n = N;
    for (int i = 1 ; i <= n-1 ; ++i)
    {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }

    dfs(1, 0);
    nextInTour[tour.back()] = 1;
    for (int i = tour.size() - 2 ; i >= 0 ; --i)
    {
        nextInTour[tour[i]] = tour[i + 1];
    }

    setHintLen(20);
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 9 ; j >= 0 ; --j)
        {
            setHint(i, 10 - j, (parent[i] & (1 << j)) > 0);
        }

        for (int j = 9 ; j >= 0 ; --j)
        {
            setHint(i, 20 - j, (nextInTour[i] & (1 << j)) > 0);
        }
    }
}

void speedrun(int subtask, int N, int start)
{
    while (start >= 2)
    {
        int par = 0, next = 0;
        for (int i = 1 ; i <= 10 ; ++i)
        {
            par *= 2;
            par += getHint(i);
        }

        for (int i = 11 ; i <= 20 ; ++i)
        {
            next *= 2;
            next += getHint(i);
        }

        goTo(par);
        start = par;
    }

    while (true)
    {
        if (start == 0) return;
        int par = 0, next = 0;
        for (int i = 1 ; i <= 10 ; ++i)
        {
            par *= 2;
            par += getHint(i);
        }

        for (int i = 11 ; i <= 20 ; ++i)
        {
            next *= 2;
            next += getHint(i);
        }

        if (next == 1) return;
        while (!goTo(next))
        {
            start = par;
            goTo(par);
            par = 0;
            for (int i = 1 ; i <= 10 ; ++i)
            {
                par *= 2;
                par += getHint(i);
            }
        }

        start = next;
    }
}

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