oj.uz

Submission #642496

# Submission time Handle Problem Language Result Execution time Memory
642496 2022-09-19T15:49:10 Z Matteo_Verz Speedrun (RMI21_speedrun) C++17
100 / 100
 136 ms 920 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 692 KB Output is correct
2 Correct 125 ms 676 KB Output is correct
3 Correct 94 ms 792 KB Output is correct
4 Correct 116 ms 692 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 804 KB Output is correct
2 Correct 111 ms 676 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 800 KB Output is correct
2 Correct 103 ms 684 KB Output is correct
3 Correct 114 ms 844 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 672 KB Output is correct
2 Correct 109 ms 700 KB Output is correct
3 Correct 136 ms 804 KB Output is correct
4 Correct 125 ms 672 KB Output is correct
5 Correct 122 ms 688 KB Output is correct
6 Correct 111 ms 792 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 732 KB Output is correct
2 Correct 121 ms 920 KB Output is correct
3 Correct 121 ms 672 KB Output is correct
4 Correct 68 ms 684 KB Output is correct
5 Correct 112 ms 672 KB Output is correct
6 Correct 131 ms 724 KB Output is correct
7 Correct 102 ms 684 KB Output is correct