Submission #1116976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116976		alecurse	Speedrun (RMI21_speedrun)	C++14	100 / 100	423 ms	1328 KiB

speedrun

#include "speedrun.h"
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int> > adj;
vector<pair<int,int> > hintss;
stack<int> s;
int root=1;
void dfs(int x, int e) {

    if(adj[x].size()==1&&x!=root) {
        if(s.empty())
            return;
        hintss[x].first=s.top();
        s.pop();
        return;
    }
    if(adj[x][0]==e) {
        hintss[x].first=adj[x][1];
    } else {
        hintss[x].first=adj[x][0];
    }
    for(int i=adj[x].size()-1;i>(adj[x][0]==e ? 1 : 0);i--) {
        if(adj[x][i]==e)
            continue;
        s.push(adj[x][i]);
    }
    for(auto b : adj[x]) {
        if(b==e) continue;
        hintss[b].second=x;
        dfs(b,x);
    }
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    adj.resize(N+1);
    hintss.resize(N+1);
    for(int i=1;i<N;i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    for(int i=1;i<=N;i++) {
        if(adj[i].size()==1) {
            root=i;
            break;
        }
    }

    dfs(root,-1);
    for(int i=1;i<=N;i++) {

    }
    setHintLen(20);
    for(int i=1;i<=N;i++) {
        for(int j=0;j<10;j++) {
            if((hintss[i].first&(1<<j))!=0) {
                setHint(i,j+1,1);
            } else {
                setHint(i,j+1,0);
            }
        }
        for(int j=0;j<10;j++) {
            if((hintss[i].second&(1<<j))!=0) {
                setHint(i,j+11,1);
            } else {
                setHint(i,j+11,0);
            }
        }
    }
}
int getparent(int x) {
    int res=0;
    for(int i=0;i<10;i++) {
        if(getHint(i+11)) {
            res|=(1<<i);
        }
    }
    return res;
}

int getchild(int x) {
    int res=0;
    for(int i=0;i<10;i++) {
        if(getHint(i+1)) {
            res|=(1<<i);
        }
    }
    return res;
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    stack<int> sospesi;
    vector<bool> vis(N+1);
    vector<int> childs(N+1);
    vector<int> parents(N+1);
    int nodo=start;

    int sizee=0;
    int count=0;

    while(true) {

        // cout<<nodo<<" "<<sospeso<<"\n";
        vis[nodo]=true;
        
        childs[nodo]=getchild(nodo);
        parents[nodo]=getparent(nodo);
        if(vis[childs[nodo]]||childs[nodo]==0) {
            if(!sospesi.empty()&&!vis[sospesi.top()]) {
                bool th = goTo(sospesi.top());
                if(th) {
                    nodo = sospesi.top();
                    sospesi.pop();
                } else {
                    th = goTo(parents[nodo]);
                    nodo = parents[nodo];
                }
            } else if(parents[nodo]!=0) {
                bool th = goTo(parents[nodo]);
                nodo = parents[nodo];
            } else {
                break;
            }
        } else {
            bool th = goTo(childs[nodo]);
            if(th) {
                nodo = childs[nodo];
            } else {
                sospesi.push(childs[nodo]);
                if(parents[nodo]==0)
                    break;
                th = goTo(parents[nodo]);
                nodo = parents[nodo];
            }
        }
        if(sizee==N)
            break;
    }

    
}

Compilation message (stderr)

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:119:22: warning: unused variable 'th' [-Wunused-variable]
  119 |                 bool th = goTo(parents[nodo]);
      |                      ^~
speedrun.cpp:99:9: warning: unused variable 'count' [-Wunused-variable]
   99 |     int count=0;
      |         ^~~~~

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