Submission #645136

#	Time	Username	Problem	Language	Result	Execution time	Memory
645136		Vanilla	Speedrun (RMI21_speedrun)	C++17	60 / 100	198 ms	920 KiB

speedrun

#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
const int maxn = 1e3 + 2;
// bool ad [maxn][maxn];

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    int deg [N + 1] = {};
    vector <int> ad [maxn];
    if (subtask == 1 || N <= 4) {
        setHintLen(N);
        for (int i = 1; i < N; i++){
            setHint(A[i], B[i], 1);
            setHint(B[i], A[i], 1);
        }
    }
    if (subtask == 2) {
        setHintLen(1);
        for (int i = 1; i < N; i++){
            deg[A[i]]++;
            deg[B[i]]++;
        }
        for (int i = 1; i <= N; i++){
            if (deg[i] > 1) setHint(i, 1, 1);
        }
    }
    if (subtask == 3) {
        setHintLen(20);
        for (int i = 1; i < N; i++){
            ad[A[i]].push_back(B[i]);
            ad[B[i]].push_back(A[i]);
        }
        for (int i = 1; i <= N; i++){
            // cout << i << ": ";
            for (int j = 0; j < ad[i].size(); j++){
                int k = ad[i][j];
                int offset = j * 10 + 1;
                for (int b = 0; b <= 9; b++) {
                    // cout << !!(k & (1 << b));
                    setHint(i, b + offset, !!(k & (1 << b)));
                }
                // cout << " ";
            }
            // cout << "\n";
        }
    }
    if (subtask == 4) {
        setHintLen(316);
        for (int i = 1; i < N; i++){
            ad[A[i]].push_back(B[i]);
            ad[B[i]].push_back(A[i]);
        }
        for (int i = 1; i <= N; i++){
            for (int j: ad[i]) {
                setHint(i, j / 4 + 1, 1);
            }
        }
    }
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    if (subtask == 1 || N <= 4) {
        auto dfs = [&] (int u, int p = -1, auto&& dfs) -> void {
            for (int i = 1; i <= N; i++){
                if (i == p || i == start) continue;
                if (getHint(i)) {
                    goTo(i);
                    dfs(i, u, dfs);
                }
            }
            if (p != -1) goTo(p);
        };
        dfs(start, -1, dfs);
    }
    if (subtask == 2) {
        if (!getHint(1)) {
            for (int i = 1; i <= N; i++){
                if (goTo(i)) {
                    start = i;
                    break;
                }
            }
        }
        for (int i = 1; i <= N; i++){
            if (i == start) continue;
            goTo(i);
            goTo(start);
        }
    }
    if (subtask == 3) {
        auto dfs = [&] (int u, int p = -1, auto&& dfs) -> void {
            int v1 = 0, v2 = 0;
            for (int i = 0; i <= 9; i++){
                v1+=((1 << i) * getHint(i + 1));
                v2+=((1 << i) * getHint(i + 11));
            }
            if (v1 && v1 != p) {
                goTo(v1);
                dfs(v1, u, dfs);
                goTo(u);
            }
            if (v2 && v2 != p) {
                goTo(v2);
                dfs(v2, u, dfs);
                goTo(u);
            }
        };
        dfs(start, -1, dfs);
    }
    if (subtask == 4) {
        auto dfs = [&] (int u, int p = -1, auto&& dfs) -> void {
            for (int i = 1; i <= 251; i++){
                if (getHint(i)) {
                    for (int j = (i - 1) * 4; j < i * 4 && j <= N; j++) {
                        if (j == p || !j) continue;
                        if (goTo(j)) {
                            dfs(j, u, dfs);
                            goTo(u);
                        }
                    }
                }
            }
        };
        dfs(start, -1, dfs);
    }
}

Compilation message (stderr)

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

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