oj.uz

Submission #992779

# Submission time Handle Problem Language Result Execution time Memory
992779 2024-06-05T07:19:48 Z 12345678 Speedrun (RMI21_speedrun) C++17
100 / 100
 153 ms 1696 KB 
#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int t, in[nx], cur, cnt;
vector<int> d[nx];

int readparent()
{
    int res=0;
    for (int i=1; i<=10; i++) if (getHint(i)) res+=(1<<(i-1));
    return res;
}

int readdestination()
{
    int res=0;
    for (int i=1; i<=10; i++) if (getHint(i+10)) res+=(1<<(i-1));
    return res;
}

void dfs(int u, int p)
{
    in[++t]=u;
    //cout<<"dfs "<<u<<' '<<p<<'\n';
    for (int i=1; i<=10; i++) setHint(u, i, (p&(1<<(i-1)))>0);
    for (auto v:d[u]) if (v!=p) dfs(v, u);    
}

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

void speedrun(int subtask, int N, int start) {
    int u=start;
    while (readparent()!=u) u=readparent(), goTo(readparent());
    cur=readdestination();
    while (cur!=0)
    {
        if (!goTo(cur)) goTo(readparent());
        else cur=readdestination();
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1196 KB Output is correct
2 Correct 124 ms 892 KB Output is correct
3 Correct 123 ms 684 KB Output is correct
4 Correct 133 ms 1696 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 1096 KB Output is correct
2 Correct 110 ms 944 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 888 KB Output is correct
2 Correct 106 ms 1180 KB Output is correct
3 Correct 127 ms 940 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 688 KB Output is correct
2 Correct 135 ms 1112 KB Output is correct
3 Correct 133 ms 688 KB Output is correct
4 Correct 111 ms 688 KB Output is correct
5 Correct 140 ms 684 KB Output is correct
6 Correct 114 ms 688 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 1120 KB Output is correct
2 Correct 147 ms 940 KB Output is correct
3 Correct 128 ms 684 KB Output is correct
4 Correct 110 ms 688 KB Output is correct
5 Correct 127 ms 1112 KB Output is correct
6 Correct 127 ms 684 KB Output is correct
7 Correct 122 ms 1112 KB Output is correct