oj.uz

Submission #1116973

# Submission time Handle Problem Language Result Execution time Memory
1116973 2024-11-22T16:57:52 Z alecurse Speedrun (RMI21_speedrun) C++14
0 / 100
 368 ms 1192 KB 
#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 */
    int sospeso=-1;
    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(count<1000) {
        count++;

        vis[nodo]=true;
        childs[nodo]=getchild(nodo);
        parents[nodo]=getparent(nodo);
        if(vis[childs[nodo]]||childs[nodo]==0) {
            if(sospeso!=-1&&!vis[sospeso]) {
                bool th = goTo(sospeso);
                if(th) {
                    nodo = sospeso;
                    sospeso=-1;
                } 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 {
                sospeso=childs[nodo];
                if(parents[nodo]==0)
                    break;
                th = goTo(parents[nodo]);
                nodo = parents[nodo];
            }
        }
        if(sizee==N)
            break;
    }

    
}

Compilation message

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

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 366 ms 824 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 350 ms 668 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 1192 KB Output is correct
2 Incorrect 350 ms 1080 KB Solution didn't visit every node
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 350 ms 1068 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 820 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -