Submission #536546

#	Time	Username	Problem	Language	Result	Execution time	Memory
536546		tqbfjotld	Speedrun (RMI21_speedrun)	C++14	100 / 100	198 ms	860 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adjl[1005];
vector<int> preord;
int pa[1005];

void dfs(int node, int p){
    preord.push_back(node);
    pa[node] = p;
    for (auto x : adjl[node]){
        if (x==p) continue;
        dfs(x,node);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    for (int x = 1; x<N; x++){
        adjl[A[x]].push_back(B[x]);
        adjl[B[x]].push_back(A[x]);
    }
    dfs(1,0);
    setHintLen(20);
    for (int x = 1; x<=N; x++){
        for (int y = 1; y<=10; y++){
            if (pa[x]&(1<<(y-1))){
                setHint(x,y,true);
            }
            else setHint(x,y,false);
        }
    }
    preord.push_back(preord[0]);
    for (int x = 0; x<N; x++){
        for (int y = 0; y<10; y++){
            if (preord[x+1]&(1<<y)){
                setHint(preord[x],y+11,true);
            }
            else setHint(preord[x],y+11,false);
        }
    }
}

bool vis[1005];

void speedrun(int subtask, int N, int start) { /* your solution here */
    int numvis = 1;
    vis[start] = true;
    int goal = -1;
    while (numvis<N){
        int par = 0;
        int nx = 0;
        for (int y = 1; y<=10; y++){
            if (getHint(y)){
                par += 1<<(y-1);
            }
        }
        for (int y = 11; y<=20; y++){
            if (getHint(y)){
                nx += 1<<(y-11);
            }
        }
        if (goal==-1) goal = nx;
        if (goTo(goal)){
            numvis += !vis[goal];
            vis[goal] = true;
            goal = -1;
        }
        else{
            assert(goTo(par));
            numvis += !vis[par];
            vis[par] = true;
        }
    }
}

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40