oj.uz

Submission #1116976

# Submission time Handle Problem Language Result Execution time Memory
1116976 2024-11-22T17:03:49 Z alecurse Speedrun (RMI21_speedrun) C++14
100 / 100
 423 ms 1328 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 */
    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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 1076 KB Output is correct
2 Correct 368 ms 668 KB Output is correct
3 Correct 386 ms 832 KB Output is correct
4 Correct 418 ms 824 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 1092 KB Output is correct
2 Correct 394 ms 924 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 1072 KB Output is correct
2 Correct 381 ms 940 KB Output is correct
3 Correct 372 ms 1184 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 1328 KB Output is correct
2 Correct 410 ms 820 KB Output is correct
3 Correct 421 ms 1088 KB Output is correct
4 Correct 415 ms 820 KB Output is correct
5 Correct 413 ms 1092 KB Output is correct
6 Correct 398 ms 968 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 928 KB Output is correct
2 Correct 423 ms 1176 KB Output is correct
3 Correct 403 ms 1076 KB Output is correct
4 Correct 375 ms 1324 KB Output is correct
5 Correct 416 ms 1068 KB Output is correct
6 Correct 410 ms 1180 KB Output is correct
7 Correct 397 ms 1176 KB Output is correct