Submission #498930

#	Time	Username	Problem	Language	Result	Execution time	Memory
498930		dxz05	Speedrun (RMI21_speedrun)	C++14	100 / 100	126 ms	1008 KiB

speedrun

#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 (stderr)

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 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40