oj.uz

Submission #538336

# Submission time Handle Problem Language Result Execution time Memory
538336 2022-03-16T15:35:02 Z joelau Speedrun (RMI21_speedrun) C++14
100 / 100
 111 ms 884 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> lst[1005], pre;

void dfs (int x, int p) {
    for (int i = 0; i < 10; ++i) if (p & (1<<i)) setHint(x,i+1,1);
    pre.push_back(x);
    for (int v: lst[x]) if (v != p) dfs(v,x);
}

void assignHints(int subtask, int N, int A[], int B[]) {
    for (int i = 1; i < N; ++i) {
        lst[A[i]].push_back(B[i]);
        lst[B[i]].push_back(A[i]);
    }
    setHintLen(20);
    dfs(1,1);
    for (int i = 0; i < N-1; ++i) for (int j = 0; j < 10; ++j) if (pre[i+1] & (1<<j)) setHint(pre[i],j+11,1);
}

int getA() {
    int ans = 0;
    for (int i = 0; i < 10; ++i) if (getHint(i+1)) ans |= (1<<i);
    return ans;
}

int getB() {
    int ans = 0;
    for (int i = 0; i < 10; ++i) if (getHint(i+11)) ans |= (1<<i);
    return ans;
}

void speedrun(int subtask, int N, int start) {
    int n = start, a = getA();
    while (n != a) {
        goTo(a), n = a, a = getA();
    }
    int b = getB();
    for (int i = 0; i < N-1; ++i) {
        while (!goTo(b)) goTo(a), n = a, a = getA();
        n = b, a = getA(), b = getB();
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 676 KB Output is correct
2 Correct 91 ms 684 KB Output is correct
3 Correct 100 ms 736 KB Output is correct
4 Correct 111 ms 684 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 704 KB Output is correct
2 Correct 76 ms 876 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 712 KB Output is correct
2 Correct 82 ms 740 KB Output is correct
3 Correct 105 ms 840 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 704 KB Output is correct
2 Correct 103 ms 712 KB Output is correct
3 Correct 83 ms 884 KB Output is correct
4 Correct 57 ms 780 KB Output is correct
5 Correct 97 ms 772 KB Output is correct
6 Correct 77 ms 792 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 796 KB Output is correct
2 Correct 95 ms 756 KB Output is correct
3 Correct 95 ms 740 KB Output is correct
4 Correct 79 ms 736 KB Output is correct
5 Correct 102 ms 776 KB Output is correct
6 Correct 84 ms 824 KB Output is correct
7 Correct 81 ms 672 KB Output is correct