oj.uz

Submission #536546

# Submission time Handle Problem Language Result Execution time Memory
536546 2022-03-13T13:49:11 Z tqbfjotld Speedrun (RMI21_speedrun) C++14
100 / 100
 198 ms 860 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[0]);
    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 165 ms 716 KB Output is correct
2 Correct 178 ms 804 KB Output is correct
3 Correct 178 ms 860 KB Output is correct
4 Correct 112 ms 740 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 712 KB Output is correct
2 Correct 191 ms 716 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 716 KB Output is correct
2 Correct 168 ms 676 KB Output is correct
3 Correct 175 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 800 KB Output is correct
2 Correct 178 ms 792 KB Output is correct
3 Correct 146 ms 716 KB Output is correct
4 Correct 163 ms 672 KB Output is correct
5 Correct 149 ms 684 KB Output is correct
6 Correct 143 ms 840 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 792 KB Output is correct
2 Correct 173 ms 732 KB Output is correct
3 Correct 198 ms 672 KB Output is correct
4 Correct 142 ms 792 KB Output is correct
5 Correct 176 ms 716 KB Output is correct
6 Correct 195 ms 672 KB Output is correct
7 Correct 180 ms 712 KB Output is correct