Submission #537058

#	Time	Username	Problem	Language	Result	Execution time	Memory
537058		dantoh000	Speedrun (RMI21_speedrun)	C++14	0 / 100	81 ms	776 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int arr1[1005][1005];
int arr2[1005][25];
vector<int> G[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){
    last = u;
    for (auto v : G[u]){
        if (v == p) continue;
        if (last == u){
            include(u, v, p);
        }
        else include(last, u, v);
        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);
}
int n;
vector<int> G_[1005];
int vis[1005];
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;
}


void dfs(int u, int p){
    ii D = proc(u);
    //printf("at %d: %d %d\n",u,D.first,D.second);
    if (goTo(D.first)){
        G_[u].push_back(D.first);
        goTo(u);
        if (D.second && goTo(D.second)){
            G_[u].push_back(D.second);
            goTo(u);
        }
    }
    else{
        //printf("adding %d %d\n",D.first,D.second);
        G_[D.first].push_back(D.second);
        G_[D.second].push_back(D.first);
    }
    if ((int)G_[u].size() == 0){
        for (int i = 1; i <= n; i++){
            if (goTo(i)){
                G_[u].push_back(i);
                goTo(u);
                break;
            }
        }
    }
    for (int i = 0; i < (int)G[u].size(); i++){
        int v = G[u][i];
        if (v == p) continue;
        goTo(v);
        dfs(v, u);
    }
    if (p != 0) goTo(p);
}



void speedrun(int subtask, int N, int start) { /* your solution here */
    n = N;
    dfs(start,0);

}

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