oj.uz

Submission #539418

# Submission time Handle Problem Language Result Execution time Memory
539418 2022-03-18T20:30:56 Z doowey Speedrun (RMI21_speedrun) C++14
100 / 100
 174 ms 1104 KB 
#include <bits/stdc++.h>
#include "speedrun.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 1010;
vector<int> T[N];

vector<int> bits(int u){
    vector<int> sol;
    for(int i = 0 ; i < 10; i ++ ){
        if((u & (1 << i))){
            sol.push_back(1);
        }
        else{
            sol.push_back(0);
        }
    }
    return sol;
}

vector<int> ord;
vector<int> A[N];
vector<int> B[N];

void dfs(int u, int p){
    A[u] = bits(p);
    B[u] = bits(0);
    ord.push_back(u);
    for(auto x : T[u]){
        if(x == p) continue;
        dfs(x, u);
    }
}

void assignHints(int subtask, int n, int AA[], int BB[]) { /* your solution here */
    for(int i = 1; i <= n-1; i ++ ){
        T[AA[i]].push_back(BB[i]);
        T[BB[i]].push_back(AA[i]);
    }
    dfs(1,-1);
    for(int i = 0 ; i + 1 < ord.size(); i ++ ){
        B[ord[i]] = bits(ord[i + 1]);
    }
    setHintLen(20);
    for(int i = 1; i <= n; i ++ ){
        for(int j = 0 ; j < A[i].size(); j ++ ){
            setHint(i, j + 1, A[i][j]);
        }
        for(int j = 0 ; j < B[i].size(); j ++ ){
            setHint(i, j + 11, B[i][j]);
        }
    }
}

int parent(){
    int x;
    int res = 0;
    for(int j = 0 ; j < 10 ; j ++ ){
        x = getHint(j + 1);
        res += x * 1ll * (1 << j);
    }
    return res;
}

int next(){
    int x;
    int res = 0;
    for(int j = 0 ; j < 10 ; j ++ ){
        x = getHint(j + 11);
        res += x * 1ll * (1 << j);
    }
    return res;
}

void speedrun(int subtask, int n, int start) { /* your solution here */
    int v;
    while(start != 1){
        v = parent();
        goTo(v);
        start = v;
    }
    int q;
    while(1){
        v = next();
        if(v == 0) break;
        while(goTo(v) == false){
            q = parent();
            start = q;
            goTo(q);
        }
        start = v;
    }
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0 ; i + 1 < ord.size(); i ++ ){
      |                     ~~~~~~^~~~~~~~~~~~
speedrun.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j = 0 ; j < A[i].size(); j ++ ){
      |                         ~~^~~~~~~~~~~~~
speedrun.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j = 0 ; j < B[i].size(); j ++ ){
      |                         ~~^~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 928 KB Output is correct
2 Correct 162 ms 984 KB Output is correct
3 Correct 173 ms 1008 KB Output is correct
4 Correct 169 ms 1008 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 980 KB Output is correct
2 Correct 154 ms 1000 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 928 KB Output is correct
2 Correct 151 ms 928 KB Output is correct
3 Correct 138 ms 1104 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 1012 KB Output is correct
2 Correct 142 ms 932 KB Output is correct
3 Correct 159 ms 928 KB Output is correct
4 Correct 154 ms 1020 KB Output is correct
5 Correct 164 ms 940 KB Output is correct
6 Correct 165 ms 928 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 1004 KB Output is correct
2 Correct 144 ms 1028 KB Output is correct
3 Correct 167 ms 940 KB Output is correct
4 Correct 125 ms 1012 KB Output is correct
5 Correct 162 ms 868 KB Output is correct
6 Correct 149 ms 932 KB Output is correct
7 Correct 127 ms 940 KB Output is correct