oj.uz

Submission #536543

# Submission time Handle Problem Language Result Execution time Memory
536543 2022-03-13T13:45:20 Z tqbfjotld Speedrun (RMI21_speedrun) C++14
40 / 100
 856 ms 756 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adjl[1005];
vector<int> preord;
int pa[1005];

void dfs(int node, int p){
    preord.push_back(node);
    pa[node] = p;
    for (auto x : adjl[node]){
        if (x==p) continue;
        dfs(x,node);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    for (int x = 1; x<N; x++){
        adjl[A[x]].push_back(B[x]);
        adjl[B[x]].push_back(A[x]);
    }
    dfs(1,0);
    setHintLen(20);
    for (int x = 1; x<=N; x++){
        for (int y = 1; y<=10; y++){
            if (pa[x]&(1<<(y-1))){
                setHint(x,y,true);
            }
            else setHint(x,y,false);
        }
    }
    preord.push_back(preord[1]);
    for (int x = 0; x<N; x++){
        for (int y = 0; y<10; y++){
            if (preord[x+1]&(1<<y)){
                setHint(preord[x],y+11,true);
            }
            else setHint(preord[x],y+11,false);
        }
    }
}

bool vis[1005];

void speedrun(int subtask, int N, int start) { /* your solution here */
    int numvis = 1;
    vis[start] = true;
    int goal = -1;
    while (numvis<N){
        int par = 0;
        int nx = 0;
        for (int y = 1; y<=10; y++){
            if (getHint(y)){
                par += 1<<(y-1);
            }
        }
        for (int y = 11; y<=20; y++){
            if (getHint(y)){
                nx += 1<<(y-11);
            }
        }
        if (goal==-1) goal = nx;
        if (goTo(goal)){
            numvis += !vis[goal];
            vis[goal] = true;
            goal = -1;
        }
        else{
            assert(goTo(par));
            numvis += !vis[par];
            vis[par] = true;
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 672 KB Output is correct
2 Correct 141 ms 672 KB Output is correct
3 Correct 170 ms 728 KB Output is correct
4 Correct 195 ms 756 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 708 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 672 KB Output is correct
2 Correct 178 ms 672 KB Output is correct
3 Correct 151 ms 744 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 672 KB Output is correct
2 Correct 177 ms 672 KB Output is correct
3 Incorrect 856 ms 716 KB Used too many wrong interactions
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 672 KB Output is correct
2 Incorrect 216 ms 672 KB Used too many wrong interactions
3 Halted 0 ms 0 KB -