Submission #1291058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291058		warrenn	Speedrun (RMI21_speedrun)	C++20	100 / 100	36 ms	480 KiB

speedrun

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

vector<int>adj[1002];
vector<int>ord;
int p[1002];

void euler(int cur,int par){
    ord.push_back(cur);
    p[cur]=par;
    for(auto x : adj[cur]){
        if(x==par)continue;
        euler(x,cur);
    }
}

void assignHints(int subtask, int n, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    for(int q=1;q<n;q++){
        adj[A[q]].push_back(B[q]);
        adj[B[q]].push_back(A[q]);
    }
    euler(1,0);

    // set hint : par nxt
    for(int q=0;q<ord.size();q++){
        int brp=0;
        if(q==ord.size()-1){
            brp=p[ord[q]];
        }
        else{
            brp=p[ord[q]];
            brp+=ord[q+1]*(1<<10);
        }

        for(int w=19;w>=0;w--){
            if((brp>>w)&1){
                setHint(ord[q],w+1,1);
            }
        }
    }
}

int brp(){
    int val=0;
    for(int q=19;q>=0;q--){
        if(getHint(q+1)){
            val+=(1<<q);
        }
    }
    return val;
}

void speedrun(int subtask, int N, int start) { /* your solution here */
   // cout<<start<<" "<<brp()<<endl;
    while(start!=1){
        int val=brp();
        goTo((val & 1023));
        start=(val & 1023);
    }

    int cur=1;
    while(true){
        int val=brp();
        int nxt=(val>>10);
        if(nxt==0)break;
        
        while(!goTo(nxt)){
            int par=(val & 1023);
            goTo(par);
            val=brp();
        }
        cur=nxt;
    }
}

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