oj.uz

Submission #536855

# Submission time Handle Problem Language Result Execution time Memory
536855 2022-03-14T06:11:05 Z tqbfjotld Speedrun (RMI21_speedrun) C++14
100 / 100
 215 ms 812 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;
    int cur = start;
    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)){
          goTo(cur);
          goTo(goal);
            numvis += !vis[goal];
            vis[goal] = true;
            cur = goal;
            goal = -1;
        }
        else{
            assert(goTo(par));
            assert(goTo(cur));
            assert(goTo(par)); //testing something

            cur = par;
            numvis += !vis[par];
            vis[par] = true;
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 704 KB Output is correct
2 Correct 156 ms 804 KB Output is correct
3 Correct 131 ms 704 KB Output is correct
4 Correct 209 ms 728 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 672 KB Output is correct
2 Correct 178 ms 804 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 812 KB Output is correct
2 Correct 191 ms 796 KB Output is correct
3 Correct 202 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 672 KB Output is correct
2 Correct 174 ms 744 KB Output is correct
3 Correct 179 ms 792 KB Output is correct
4 Correct 174 ms 712 KB Output is correct
5 Correct 169 ms 700 KB Output is correct
6 Correct 194 ms 796 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 672 KB Output is correct
2 Correct 192 ms 712 KB Output is correct
3 Correct 211 ms 720 KB Output is correct
4 Correct 215 ms 792 KB Output is correct
5 Correct 180 ms 720 KB Output is correct
6 Correct 193 ms 704 KB Output is correct
7 Correct 163 ms 724 KB Output is correct