oj.uz

Submission #1119351

# Submission time Handle Problem Language Result Execution time Memory
1119351 2024-11-26T21:35:32 Z Bula Speedrun (RMI21_speedrun) C++17
100 / 100
 213 ms 1388 KB 
#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
const int Nx = 1e3 + 5;
vector<int> adj[Nx], par(Nx), ord;
void dfs(int v, int p){
    par[v] = p;
    ord.push_back(v);
    for(auto x : adj[v]){
        if(x == p) continue;
        dfs(x, v);
    }
}
void assignHints(int subtask, int n, int A[], int B[]){
    for(int i = 1; i <= n - 1; i++){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    setHintLen(20); 
    dfs(1, 0);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 10; j++){
            if(par[i] & (1 << j)) setHint(i, j + 1, 1);
        }
    }
    for(int i = 1; i < ord.size(); i++){
        for(int j = 0; j < 10; j++){
            if(ord[i] & (1 << j)) setHint(ord[i - 1], j + 11, 1);
        }
    }
}

void speedrun(int subtask, int n, int start){
    while(start != 1){
        int p = 0;
        for(int j = 1; j <= 10; j++){
            p += getHint(j) * (1 << (j - 1));
        }
        goTo(p);
        start = p;
    }
    set<int> st;
    int targ = 0, cur = start;
    while(st.size() < n){
        st.insert(cur);
        int p = 0, nxt = 0;
        for(int j = 1; j <= 10; j++){
            p += getHint(j) * (1 << (j - 1));
            nxt += getHint(j + 10) * (1 << (j - 1));
        }
        if(targ > 0 && goTo(targ)){
            cur = targ;
            targ = 0;
        }else if(nxt > 0 && st.find(nxt) == st.end() && goTo(nxt)){
            cur = nxt;
        }
        else{
            goTo(p);
            cur = p;
            if(targ == 0) targ = nxt;
        }
    }
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 1; i < ord.size(); i++){
      |                    ~~^~~~~~~~~~~~
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:44:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     while(st.size() < n){
      |           ~~~~~~~~~~^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1140 KB Output is correct
2 Correct 208 ms 668 KB Output is correct
3 Correct 194 ms 1108 KB Output is correct
4 Correct 199 ms 1144 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1120 KB Output is correct
2 Correct 165 ms 1152 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 1184 KB Output is correct
2 Correct 185 ms 924 KB Output is correct
3 Correct 176 ms 1272 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 1108 KB Output is correct
2 Correct 190 ms 884 KB Output is correct
3 Correct 204 ms 1380 KB Output is correct
4 Correct 196 ms 1388 KB Output is correct
5 Correct 192 ms 916 KB Output is correct
6 Correct 207 ms 1264 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 1124 KB Output is correct
2 Correct 200 ms 1140 KB Output is correct
3 Correct 213 ms 1292 KB Output is correct
4 Correct 172 ms 1384 KB Output is correct
5 Correct 191 ms 1344 KB Output is correct
6 Correct 202 ms 1136 KB Output is correct
7 Correct 163 ms 1188 KB Output is correct