oj.uz

Submission #764936

# Submission time Handle Problem Language Result Execution time Memory
764936 2023-06-24T06:43:15 Z SeDunion Speedrun (RMI21_speedrun) C++17
63 / 100
 274 ms 884 KB 
#include "speedrun.h"
#include <vector>
#include <iostream>
#include <stack>

using namespace std;

const int MAXN = 1002;

vector<int>g[MAXN];

void setH(int pos, int val, int l, int r) {
    // cout << pos << " " << val << " " << l << " " << r << endl;
    for (int i = 0 ; i < r - l + 1 ; ++ i) {
        setHint(pos, i + l, (val >> i) & 1);
    }
}

void dfs(int v, int p) {
    // cout << v << " " << p << endl;
    setH(v, p, 1, 10);
    int child = 0;
    vector<int>children;
    for (int to : g[v]) if (to != p) {
        child = to;
        dfs(to, v);
        children.emplace_back(to);
    }
    setH(v, child, 11, 20);
    int m = children.size();
    for (int i = 0 ; i < m ; ++ i) {
        int x = children[i];
        int y = children[i == m - 1 ? 0 : i + 1];
        setH(x, y, 21, 30);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    // cout << "assignHints" << endl;
    // for every node, we want to insert:
    // 1) its parent
    // 2) its sibling
    // 3) its child
    setHintLen(30);
    for (int i = 1 ; i < N ; ++ i) {
        g[A[i]].emplace_back(B[i]);
        g[B[i]].emplace_back(A[i]);
    }
    dfs(1, 0);
    // cout << "lol" << endl;
}

int used[MAXN];

int getH(int l, int r) {
    int ret = 0;
    for (int i = 0 ; i < r - l + 1 ; ++ i) {
        ret += (1 << i) * getHint(i + l);
    }
    return ret;
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    // cout << "Speedrun" << endl;
    int x;
    while (x = getH(1, 10)) {
        // cout << x << endl;
        goTo(x);
    }
    // cout << "here " << x << endl;
    // now where are at the root
    // we can do dfs now
    used[0] = 1;
    int v = 1;
    int rep = 0;
    while (1) {
        rep++;
        // cout << "ver " << v << endl;
        used[v] = 1;
        int c = getH(11, 20);
        if (!used[c]) {
            // cout << v << " -> " << c << endl;
            goTo(c);
            v = c;
            continue;
        }
        int s = getH(21, 30);
        if (!used[s]) {
            int p = getH(1, 10);
            // cout << v << " -> " << p << " -> " << s << endl;
            goTo(p);
            goTo(s);
            v = s;
            continue;
        }
        int p = getH(1, 10);
        if (!p) break;
        // cout << v << " -----> " << p << endl;
        goTo(p);
        v = p;
    }
}

Compilation message

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:66:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   66 |     while (x = getH(1, 10)) {
      |            ~~^~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 672 KB Output is correct
2 Correct 260 ms 752 KB Output is correct
3 Correct 165 ms 772 KB Output is correct
4 Correct 244 ms 884 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 712 KB Output is correct
2 Correct 241 ms 728 KB Output is correct
3 Correct 223 ms 672 KB Output is correct
4 Correct 243 ms 760 KB Output is correct
5 Correct 212 ms 672 KB Output is correct
6 Correct 157 ms 724 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 213 ms 748 KB Partial solution
2 Partially correct 247 ms 744 KB Partial solution
3 Partially correct 265 ms 672 KB Partial solution
4 Partially correct 220 ms 744 KB Partial solution
5 Partially correct 206 ms 672 KB Partial solution
6 Partially correct 188 ms 712 KB Partial solution
7 Partially correct 144 ms 760 KB Partial solution