oj.uz

Submission #543936

# Submission time Handle Problem Language Result Execution time Memory
543936 2022-03-31T16:17:55 Z eecs Speedrun (RMI21_speedrun) C++17
100 / 100
 185 ms 884 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

void assignHints(int, int n, int *U, int *V) {
    setHintLen(20);
    vector<vector<int>> G(n + 1);
    for (int i = 1; i < n; i++) {
        G[U[i]].push_back(V[i]), G[V[i]].push_back(U[i]);
    }
    int lst = 0;
    function<void(int, int)> dfs = [&](int u, int fa) {
        if (lst) for (int i = 0; i < 10; i++) setHint(lst, i + 1, u >> i & 1);
        lst = u;
        for (int i = 0; i < 10; i++) setHint(u, i + 11, fa >> i & 1);
        for (int v : G[u]) if (v ^ fa) dfs(v, u);
    };
    dfs(1, 0);
    setHint(lst, 1, 1);
}

void speedrun(int, int n, int s) {
    while (1) {
        int fa = 0;
        for (int i = 0; i < 10; i++) if (getHint(i + 1)) fa |= 1 << i;
        if (s == fa) break;
        while (!goTo(fa)) {
            int nxt = 0;
            for (int i = 0; i < 10; i++) if (getHint(i + 11)) nxt |= 1 << i;
            goTo(nxt);
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 672 KB Output is correct
2 Correct 183 ms 744 KB Output is correct
3 Correct 179 ms 672 KB Output is correct
4 Correct 165 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 680 KB Output is correct
2 Correct 161 ms 744 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 768 KB Output is correct
2 Correct 185 ms 768 KB Output is correct
3 Correct 144 ms 804 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 668 KB Output is correct
2 Correct 142 ms 696 KB Output is correct
3 Correct 165 ms 692 KB Output is correct
4 Correct 149 ms 884 KB Output is correct
5 Correct 185 ms 680 KB Output is correct
6 Correct 181 ms 672 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 876 KB Output is correct
2 Correct 172 ms 684 KB Output is correct
3 Correct 122 ms 700 KB Output is correct
4 Correct 178 ms 744 KB Output is correct
5 Correct 179 ms 684 KB Output is correct
6 Correct 185 ms 680 KB Output is correct
7 Correct 183 ms 672 KB Output is correct