Submission #642496

#	Time	Username	Problem	Language	Result	Execution time	Memory
642496		Matteo_Verz	Speedrun (RMI21_speedrun)	C++17	100 / 100	136 ms	920 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
#ifdef BLAT
   #include "debug/debug.hpp"
#else
   #define debug(x...)
#endif

using namespace std;
using Graph = vector <vector <int>>;

void dfs(int node, Graph &g, vector <int> &preorder, vector <int> &p, int parent = 0) {
    preorder.push_back(node);
    p[node] = parent;
    for (auto it : g[node])
        if (it != parent)
            dfs(it, g, preorder, p, node);
}

void setHintsParents(vector <int> &parent) {
    for (int i = 1; i < parent.size(); i++) {
        int p = parent[i];
        
        for (int j = 0; (1 << j) <= p; j++)
            if (p & (1 << j))
                setHint(i, j + 1, true);
    }
}

void setHintsPreorder(vector <int> &preorder) {
    for (int i = 0; i + 1 < preorder.size(); i++) {
        int nxt = preorder[i + 1];

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

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

    vector <int> preorder, parent(1 + N);
    dfs(1, g, preorder, parent);

    debug(preorder);

    // set hint length of 20 bits
    // first 10 for parent, next 10 for next node in preorder
    setHintLen(20);
    setHintsParents(parent);
    setHintsPreorder(preorder);
}

pair <int, int> readHint(int node) {
    int parent, nxt;
    parent = nxt = 0;
    
    for (int i = 1; i <= 20; i++) {
        if (getHint(i)) {
            if (i <= 10) 
                parent |= (1 << (i - 1));
            else 
                nxt |= (1 << (i - 11));
        }
    }

    return make_pair(parent, nxt);
}

void speedrun(int subtask, int N, int start) {
    assert(getLength() == 20);

    // first, get to the root
    int currnode = start;
    while (currnode != 1) {
        int parent = readHint(currnode).first;
        goTo(parent);
        currnode = parent;
    }
    
    // now visit all nodes
    for (int visited = 2; visited <= N; visited++) {
        auto [parent, nxt] = readHint(currnode);
        assert(nxt != 0);
        debug(currnode, parent, nxt);
        
        while (goTo(nxt) == false) {
            goTo(parent);
            currnode = parent;
            parent = readHint(currnode).first;
        }

        goTo(nxt);
        currnode = nxt;
    }
}

Compilation message (stderr)

speedrun.cpp: In function 'void setHintsParents(std::vector<int>&)':
speedrun.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 1; i < parent.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
speedrun.cpp: In function 'void setHintsPreorder(std::vector<int>&)':
speedrun.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i + 1 < preorder.size(); i++) {
      |                     ~~~~~~^~~~~~~~~~~~~~~~~

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