oj.uz

Submission #498930

# Submission time Handle Problem Language Result Execution time Memory
498930 2021-12-26T18:36:34 Z dxz05 Speedrun (RMI21_speedrun) C++14
100 / 100
 126 ms 1008 KB 
#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;

int ord[1001];

vector<int> vec;
void dfs(int v, int p){
    ord[v] = vec.size();
    vec.push_back(v);

    if (v != p){
        for (int i = 0; i < 10; i++){
            if (p & (1 << i)) setHint(v, i + 11, true);
        }
    }

    for (int u : g[v]){
        if (u != p){
            dfs(u, v);
        }
    }

}

void assignHints(int subtask, int N, int A[], int B[]) {
    setHintLen(20);

    g.resize(N + 1);
    for (int i = 1; i < N; i++){
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }

    dfs(1, 1);

    for (int i = 1; i <= N; i++){
        int j = vec[(ord[i] + 1) % N];
        for (int k = 0; k < 10; k++){
            if (j & (1 << k)) setHint(i, k + 1, true);
        }
    }

}

int get_next(){
    int v = 0;
    for (int i = 0; i < 10; i++){
        if (getHint(i + 1)) v |= 1 << i;
    }
    return v;
}

int get_parent(){
    int v = 0;
    for (int i = 0; i < 10; i++){
        if (getHint(i + 11)) v |= 1 << i;
    }
    return v;
}

void speedrun(int subtask, int N, int start) {
    set<int> vis;
    vis.insert(start);

    int x = start;
    while (vis.size() < N){
        int u = get_next();
        if (u > 0 && goTo(u)){
            x = u;
            vis.insert(u);
            continue;
        }

        while (true){
            int v = get_parent();
            if (vis.size() == N) return;
            if (v > 0){
                if (goTo(v)){
                    x = v;
                    vis.insert(v);
                }
            }
            if (vis.size() == N) return;
            if (goTo(u)){
                x = u;
                vis.insert(u);
                break;
            }
        }

    }
}

Compilation message

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:70:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |     while (vis.size() < N){
      |            ~~~~~~~~~~~^~~
speedrun.cpp:80:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |             if (vis.size() == N) return;
      |                 ~~~~~~~~~~~^~~~
speedrun.cpp:87:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |             if (vis.size() == N) return;
      |                 ~~~~~~~~~~~^~~~
speedrun.cpp:69:9: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   69 |     int x = start;
      |         ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 716 KB Output is correct
2 Correct 115 ms 1008 KB Output is correct
3 Correct 118 ms 696 KB Output is correct
4 Correct 99 ms 748 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 688 KB Output is correct
2 Correct 100 ms 732 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 800 KB Output is correct
2 Correct 78 ms 748 KB Output is correct
3 Correct 96 ms 744 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 676 KB Output is correct
2 Correct 106 ms 724 KB Output is correct
3 Correct 118 ms 660 KB Output is correct
4 Correct 89 ms 676 KB Output is correct
5 Correct 122 ms 668 KB Output is correct
6 Correct 100 ms 776 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 788 KB Output is correct
2 Correct 97 ms 716 KB Output is correct
3 Correct 90 ms 688 KB Output is correct
4 Correct 124 ms 720 KB Output is correct
5 Correct 104 ms 772 KB Output is correct
6 Correct 105 ms 908 KB Output is correct
7 Correct 83 ms 660 KB Output is correct