oj.uz

Submission #538343

# Submission time Handle Problem Language Result Execution time Memory
538343 2022-03-16T15:44:59 Z dantoh000 Speedrun (RMI21_speedrun) C++14
0 / 100
 115 ms 800 KB 
#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;
    }
    //printf("done with %d, checking %d\n",u,togoto);
    if (togoto && goTo(togoto)){
        dfs(togoto, u);
        goTo(u);
    }

}



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

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 800 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 50 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 Incorrect 115 ms 756 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 676 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 55 ms 744 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -