oj.uz

Submission #764952

# Submission time Handle Problem Language Result Execution time Memory
764952 2023-06-24T06:55:56 Z SeDunion Speedrun (RMI21_speedrun) C++17
100 / 100
 204 ms 956 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);
    }
}

vector<int>vec;

void dfs(int v, int p) {
    // cout << v << " " << p << endl;
    setH(v, p, 1, 10);
    vec.emplace_back(v);
    for (int to : g[v]) if (to != p) {
        dfs(to, v);
    }
}

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(20);
    for (int i = 1 ; i < N ; ++ i) {
        g[A[i]].emplace_back(B[i]);
        g[B[i]].emplace_back(A[i]);
    }
    dfs(1, 0);
    for (int i = 0 ; i < N - 1 ; ++ i) {
        int x = vec[i];
        int y = vec[i + 1];
        setH(x, y, 11, 20);
    }
    // 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;
    stack<int>s;
    s.push(v);
    while (1) {
        used[v] = 1;
        int u = getH(11, 20);
        // cout << v << " " << u << endl;
        if (!u) break;
        while (!goTo(u)) {
            s.pop();
            goTo(s.top());
        }
        s.push(u);
    }
}

Compilation message

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

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 736 KB Output is correct
2 Correct 124 ms 744 KB Output is correct
3 Correct 145 ms 824 KB Output is correct
4 Correct 186 ms 764 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 840 KB Output is correct
2 Correct 152 ms 784 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 800 KB Output is correct
2 Correct 148 ms 956 KB Output is correct
3 Correct 125 ms 812 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 728 KB Output is correct
2 Correct 181 ms 760 KB Output is correct
3 Correct 124 ms 788 KB Output is correct
4 Correct 152 ms 728 KB Output is correct
5 Correct 204 ms 704 KB Output is correct
6 Correct 164 ms 728 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 720 KB Output is correct
2 Correct 167 ms 708 KB Output is correct
3 Correct 134 ms 728 KB Output is correct
4 Correct 169 ms 880 KB Output is correct
5 Correct 183 ms 764 KB Output is correct
6 Correct 162 ms 672 KB Output is correct
7 Correct 146 ms 720 KB Output is correct