oj.uz

Submission #537064

# Submission time Handle Problem Language Result Execution time Memory
537064 2022-03-14T10:58:28 Z dantoh000 Speedrun (RMI21_speedrun) C++14
0 / 100
 75 ms 800 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
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];
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 (D.first && 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{
        if (D.first){
            //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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 672 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 58 ms 672 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 47 ms 800 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

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