Submission #503693

#	Time	Username	Problem	Language	Result	Execution time	Memory
503693		blue	Speedrun (RMI21_speedrun)	C++17	100 / 100	130 ms	920 KiB

speedrun

#include "speedrun.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

using vi = vector<int>;
using vvi = vector<int>;
#define sz(x) int(x.size())

const int maxN = 1'000;


vi visit(1+maxN, 0);
vi edge[1+maxN];
vi ord;
vi par(1+maxN, 0);

void dfs(int u, int p)
{
    par[u] = p;
    ord.push_back(u);
    for(int v: edge[u])
    {
        if(v == p) continue;
        dfs(v, u);
    }
}

void assignHints(int subtask, int N, int A[], int B[])
{
    // cerr << "assign called\n";
    for(int e = 1; e <= N-1; e++)
    {
        edge[A[e]].push_back(B[e]);
        edge[B[e]].push_back(A[e]);
    }
    dfs(1, 0);

    setHintLen(20);

    for(int u = 1; u <= N; u++)
        for(int b = 0; b < 10; b++)
            if(par[u] & (1 << b))
                setHint(u, b+1, 1);

    for(int x = 0; x < N; x++)
    {
        int u = ord[x];
        int v = ord[(x+1)%N];

        for(int b = 0; b < 10; b++)
            if(v & (1 << b))
                setHint(u, b+11, 1);
    }

    // cerr << "assigned!\n";

    // for(int u = 1; u <= N; u++) cerr << "par " << u << " = " << par[u] << '\n';
}

void speedrun(int subtask, int N, int curr)
{
    int z = 0;

    vi visit(1+N, 0);
    visit[curr] = 1;
    int visit_count = 1;

    // cerr << "curr = " << curr << '\n';

    while(visit_count < N)
    {
        // cerr << "start visit count = " << visit_count << '\n';
        int target = 0;
        for(int b = 0; b < 10; b++)
            target += (1 << b) * getHint(11+b);

        // cerr << "next target = " << target << '\n';

        while(1)
        {
            // cerr << "visit count = " << visit_count << '\n';
            // z++;
            // if(z > 20) break;
            if(goTo(target))
            {
                // cerr << "! travelled to " << target << '\n';
                if(!visit[target]) visit_count++;
                // cerr << visit_count << '\n';
                visit[target] = 1;
                curr = target;
                // cerr << "1curr = " << curr << '\n';
                break;
            }

            // cerr << "21curr = " << curr << '\n';

            int par = 0;
            for(int b = 0; b < 10; b++)
                par += (1<<b) * getHint(1+b);

            // cerr << "par = " << par << '\n';

            goTo(par);
            // cerr << "op = " << goTo(par) << '\n';
            // cerr << "travelled to " << par << '\n';
            curr = par;
            // cerr << "2curr = " << curr << '\n';
        }
        // if(z > 20) break;
    }
}

Compilation message (stderr)

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:64:9: warning: unused variable 'z' [-Wunused-variable]
   64 |     int z = 0;
      |         ^

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