oj.uz

Submission #764909

# Submission time Handle Problem Language Result Execution time Memory
764909 2023-06-24T06:27:42 Z vjudge1 Speedrun (RMI21_speedrun) C++17
0 / 100
 3500 ms 736 KB 
#include "speedrun.h"
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 1002;

vector<int>g[MAXN];

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

void dfs(int v, int p) {
    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 */
    // 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);
}

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 */
    int x;
    while (x = getH(1, 10)) {
        goTo(x);
    }
    // now where are at the root
    // we can do dfs now
    used[0] = 1;
    int v = 1;
    while (1) {
        used[v] = 1;
        int c = getH(11, 20);
        if (!used[c]) {
            goTo(c);
            continue;
        }
        int s = getH(21, 30);
        if (!used[s]) {
            int p = getH(1, 10);
            goTo(p);
            goTo(s);
            continue;
        }
        int p = getH(1, 10);
        if (!p) break;
        goTo(p);
    }
}

Compilation message

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

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3518 ms 672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.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 #3
0.0 / 19.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 #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3538 ms 716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3507 ms 736 KB Time limit exceeded
2 Halted 0 ms 0 KB -