Submission #593461

#	Time	Username	Problem	Language	Result	Execution time	Memory
593461		pakhomovee	Speedrun (RMI21_speedrun)	C++17	100 / 100	234 ms	928 KiB

speedrun

#include "speedrun.h"
#include <vector>
#include <iostream>
#include <set>

using namespace std;

vector<pair<int, int>> gg;
vector<int> ord;
vector<int> ids;
int id = 0;

void dfs(int v, vector<vector<int>> &g, int p) {
    gg[v].first = p;
    ord.push_back(v);
    ids[v] = id++;
    for (int u : g[v]) {
        if (u != p) {
            dfs(u, g, v);
        }
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    vector<vector<int>> g(N);
    for (int i = 1; i < N; ++i) {
        int u = A[i], v = B[i];
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    gg.resize(N);
    ids.resize(N);
    dfs(0, g, 0);
    for (int i = 0; i < N; ++i) {
        gg[i].second = ord[(ids[i] + 1) % N];
    }
    for (int i = 0; i < N; ++i) {
        int val = gg[i].first * (1 << 10) + gg[i].second;
        //cout << i << ' ' << gg[i].second << endl;
        for (int j = 0; j < 20; ++j) {
            if ((1 << j) & val) {
                setHint(i + 1, j + 1, 1);
            } else {
                setHint(i + 1, j + 1, 0);
            }
        }
    }
    cout << endl;
}

set<int> vis;
int n;

void work(int v, int nx) {
    vis.insert(v);
    int nxt = 0;
    int par = 0;
    for (int j = 0; j < 10; ++j) {
        nxt += (1 << j) * getHint(j + 1);
    }
    for (int j = 10; j < 20; ++j) {
        par += (1 << (j - 10)) * getHint(j + 1);
    }
    if (nx == -1) {
        nx = nxt;
    }
    if (vis.size() == n) {
        return;
    }
    //cout << v << ' ' << par << ' ' << nxt << endl;
    if (goTo(nx + 1)) {
        work(nx, -1);
    } else {
        goTo(par + 1);
        work(par, nx);
    }
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    n = N;
    work(start - 1, -1);
}

Compilation message (stderr)

speedrun.cpp: In function 'void work(int, int)':
speedrun.cpp:69:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     if (vis.size() == n) {
      |         ~~~~~~~~~~~^~~~

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40