oj.uz

Submission #537112

# Submission time Handle Problem Language Result Execution time Memory
537112 2022-03-14T14:36:12 Z siewjh Speedrun (RMI21_speedrun) C++17
100 / 100
 117 ms 840 KB 
#include "speedrun.h"
#include <vector>
using namespace std;
const int MAXN = 1005;
vector<int> adjlist[MAXN];
int p[MAXN], tour[MAXN];
int ind = 0;
void dfs(int x, int par){
    p[x] = par; tour[ind++] = x;
    for (int nxt : adjlist[x]){
        if (nxt == par) continue;
        dfs(nxt, x);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) {
    setHintLen(20);
    for (int i = 1; i < N; i++){
        int x = A[i], y = B[i];
        adjlist[x].push_back(y);
        adjlist[y].push_back(x);
    }
    dfs(1, -1);
    for (int i = 2; i <= N; i++)
        for (int k = 0; k <= 9; k++)
            if (p[i] & (1 << k))
                setHint(i, k + 1, 1);
    for (int i = 0; i < N; i++)
        for (int k = 0; k <= 9; k++)
            if (tour[(i + 1) % N] & (1 << k))
                setHint(tour[i], k + 11, 1);
}

void speedrun(int subtask, int N, int start) {
    int curr = start;
    do{
        int nxt = 0;
        for (int k = 0; k <= 9; k++)
            if (getHint(k + 11))
                nxt += (1 << k);
        while (!goTo(nxt)){
            int par = 0;
            for (int k = 0; k <= 9; k++)
                if (getHint(k + 1))
                    par += (1 << k);
            curr = par;
            goTo(par);
        }
        curr = nxt;
    } while (curr != start);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 796 KB Output is correct
2 Correct 102 ms 728 KB Output is correct
3 Correct 99 ms 700 KB Output is correct
4 Correct 94 ms 712 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 700 KB Output is correct
2 Correct 90 ms 672 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 708 KB Output is correct
2 Correct 105 ms 748 KB Output is correct
3 Correct 102 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 700 KB Output is correct
2 Correct 98 ms 700 KB Output is correct
3 Correct 91 ms 840 KB Output is correct
4 Correct 73 ms 692 KB Output is correct
5 Correct 109 ms 836 KB Output is correct
6 Correct 108 ms 712 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 672 KB Output is correct
2 Correct 117 ms 708 KB Output is correct
3 Correct 103 ms 684 KB Output is correct
4 Correct 106 ms 672 KB Output is correct
5 Correct 92 ms 704 KB Output is correct
6 Correct 81 ms 700 KB Output is correct
7 Correct 87 ms 708 KB Output is correct