Submission #992779

#	Time	Username	Problem	Language	Result	Execution time	Memory
992779		12345678	Speedrun (RMI21_speedrun)	C++17	100 / 100	153 ms	1696 KiB

speedrun

#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 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40