Submission #538344

#	Time	Username	Problem	Language	Result	Execution time	Memory
538344		dantoh000	Speedrun (RMI21_speedrun)	C++14	0 / 100	115 ms	1004 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
vector<int> G[1005];
int pa[1005];
int pre[1005];
int last = 0;
void include(int u, int v, int w){

    for (int j = 1; j <= 10; j++){
        if ((v>>(j-1))&1) setHint(u,j,1);
    }

    for (int j = 11; j <= 20; j++){
        if ((w>>(j-11))&1) setHint(u,j,1);
    }
}
void setup(int u, int p){
    pre[last] = u;
    if (last){

        include(last, pa[last], u);
    }
    pa[u] = p;
    last = u;
    for (auto v : G[u]){
        if (v == p) continue;
        setup(v,u);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    for (int i = 1; i < N; i++){
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    setup(1, 0);
    include(last, pa[last], 0);
}
int n;
ii proc(int u){
    ii x = ii(0,0);
    for (int i = 1; i <= 10; i++){
        if (getHint(i)) x.first += (1<<(i-1));
    }
    for (int i = 11; i <= 20; i++){
        if (getHint(i)) x.second += (1<<(i-11));
    }
    return x;
}

int getroot(int x){
    while (x){
        ii D = proc(x);
        //printf("%d --> %d\n",x,D.first);
        if (D.first){
            goTo(D.first);
            x = D.first;
        }
        else break;
    }
    return x;
}
int togoto = 0;
void dfs(int u, int p){
    ii D = proc(u);
    //printf("at %d: %d %d\n",u,D.first,D.second);

    if (goTo(D.second)){
        dfs(D.second, u);
        goTo(u);
    }
    else{
        togoto = D.second;
        return;
    }
    while (true){
        //printf("done with %d, checking %d\n",u,togoto);
        if (togoto && goTo(togoto)){
            dfs(togoto, u);
            goTo(u);
        }
        else break;
    }

}



void speedrun(int subtask, int N, int start) { /* your solution here */
    n = N;
    int root = getroot(start);
    //printf("%d ",root);
    dfs(root,0);

}

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