Submission #1244485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244485		Ice_man	Speedrun (RMI21_speedrun)	C++20	100 / 100	39 ms	5216 KiB

speedrun

#include "speedrun.h"
#include <iostream>
#define maxn 100005
#include <vector>

int par[maxn], child[maxn];


std::vector <int> v[maxn];
std::vector <int> m[maxn];


bool used[maxn];
int next_used = 0;
int br;

std::vector <int> tour;


void dfs(int node, int pp)
{
    tour.push_back(node);
    for(auto& nb : v[node])
    {
        if(nb == pp)
            continue;

        par[nb] = node;
        dfs(nb, node);
    }
}



void assignHints(int subtask, int N, int A[], int B[])
{
    br = N;

    for(int i = 1; i <= N - 1; i++)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }

    setHintLen(20);
    for(int i = 1; i <= N; i++)
    {

        m[i].resize(20);
        for(int j = 0; j < 20; j++)
            m[i][j] = 0;
    }

    dfs(1, -1);

    for(int i = 0; i < tour.size() - 1; i++)
        child[tour[i]] = tour[i + 1];
    child[tour.back()] = tour.back();

    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j < 10; j++)
            if((1 << j) & par[i])
                setHint(i, j + 1, 1);

        for(int j = 0; j < 10; j++)
            if((1 << j) & child[i])
                setHint(i, j + 11, 1);
    }
}


int to[maxn], p[maxn];


void speedrun(int subtask, int N, int start)
{
    int node = start;

    while(node != 1)
    {
        int tt = 0;
        for(int i = 0; i < 10; i++)
            if(getHint(i + 1) == 1)
                tt += (1 << i);

        bool lamp = goTo(tt);
        if(lamp == false)
            std::cout << 1 / 0 << "\n";

        node = tt;
    }

    while(true)
    {
        int go = 0;
        for(int i = 0; i < 10; i++)
            if(getHint(i + 11) == 1)
                go += (1 << i);

        if(go == node)
          break;

        while(true)
        {
            if(goTo(go) == true)
            {
                node = go;
                break;
            }

            int p = 0;
            for(int i = 0; i < 10; i++)
                if(getHint(i + 1) == 1)
                    p += (1 << i);

            bool cc = goTo(p);
            node = p;

            if(cc == false)
                std::cout << 1 / 0 << "\n";
        }
    }
}

Compilation message (stderr)

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:89:28: warning: division by zero [-Wdiv-by-zero]
   89 |             std::cout << 1 / 0 << "\n";
      |                          ~~^~~
speedrun.cpp:121:32: warning: division by zero [-Wdiv-by-zero]
  121 |                 std::cout << 1 / 0 << "\n";
      |                              ~~^~~

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