Submission #645206

#	Time	Username	Problem	Language	Result	Execution time	Memory
645206		Vanilla	Speedrun (RMI21_speedrun)	C++17	60 / 100	210 ms	824 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);
            }
        }
    }
    if (subtask == 5) { // left child right sibling ... left|right|parent
        setHintLen(20);
        for (int i = 1; i < N; i++){
            ad[A[i]].push_back(B[i]);
            ad[B[i]].push_back(A[i]);
        }
        vector <int> bt [maxn];
        int l[maxn] = {}, r [maxn] = {}, pr[maxn] = {};
        auto dfs = [&] (int i, int p, auto&& dfs) -> void {
            for (int j = 0; j < ad[i].size(); j++){
                if (ad[i][j] == p) {
                    ad[i].erase(ad[i].begin() + j);
                    break;
                }
            }
            if (!ad[i].empty()) l[i] = ad[i][0];
            for (int j = 1; j < ad[i].size(); j++){
                assert(ad[i][j] != p);
                r[ad[i][j-1]] = ad[i][j];
            }
            for (int j: ad[i]) {
                dfs(j, i, dfs);
            }
            pr[i] = p;

        };
        dfs(1, -1, dfs);
        for (int i = 1; i <= N; i++){
            // if (!l[i]) l[i] = pr[pr[i]], setHint(i, 21, 1);
            if (!r[i]) r[i] = pr[pr[i]], setHint(i, 20, 1);
            for (int b = 0; b <= 8; b++){
                setHint(i, b + 1, (l[i] & (1 << b)));
            }
            for (int b = 0; b <= 9; b++){
                setHint(i, b + 10, (r[i] & (1 << b)));
            }
            // cout << i << " " << l[i] << " " << r[i] << " " << pr[i] << "\n";
            // if (l[i]) cout << i << " " << l[i] << "\n";
            // if (r[i]) cout << i << " " << r[i] << "\n";
        }
    }
}

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);
    }
    if (subtask == 5) {
        srand(time(NULL));
        int mp [maxn] = {};
        int vis [maxn] = {};
        auto dfs = [&] (int u, int p = 0, auto&& dfs) -> void {
            int l = 0, r = 0;
            for (int i = 0; i <= 8; i++){
                l+=((1 << i) * getHint(i + 1));
            }
            for (int i = 0; i <= 9; i++){
                r+=((1 << i) * getHint(i + 10));
            }
            
            if (l & (1 << 9)) l^=(1 << 9);
            if (mp[u]) {
                l = mp[u];
            }
            // cout << u << " " << l << " " << r << "\n";
            if (l != 0 && l != r && l != p && l <= N && goTo(l)) {
                vis[l] = 1;
                goTo(l);
                dfs(l, u, dfs);
                goTo(u);
                mp[u] = l;
            }
            else {
                l^=(1 << 9);
                if (l != 0 && l != r && l != p && l <= N && goTo(l)) {
                    vis[l] = 1;
                    goTo(l);
                    dfs(l, u, dfs);
                    goTo(u);
                    mp[u] = l;
                }
            }
            // return;
            if (r != 0 && !getHint(20) && p) {
                vis[r] = 1;
                goTo(p);
                goTo(r);
                dfs(r, p, dfs);
                goTo(p);
                goTo(u);
            }
        };
        int p = 0;
        int s = start;
        while (s != 1) {
            int r = 0;
            for (int i = 0; i <= 9; i++){
                r+=((1 << i) * (getHint(i + 10)));
            }
            if (!p) {
                dfs(s, 0, dfs);
                for (int i = 1; i <= N; i++){
                    if (vis[i] || i == s || i == r) continue;
                    if (goTo(i)) {
                        p = i;
                        goTo(s);
                    }
                }
            }
            // cout << s << " " << r << " " << p << "\n";
            if (getHint(20)) {
                goTo(p);
                s = p;
                p = r;
            }
            else {
                goTo(p);
                goTo(r);
                s = r;
            }
        }
        dfs(s, -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++){
      |                             ~~^~~~~~~~~~~~~~
speedrun.cpp: In instantiation of 'assignHints(int, int, int*, int*)::<lambda(int, int, auto:23&&)> [with auto:23 = assignHints(int, int, int*, int*)::<lambda(int, int, auto:23&&)>&]':
speedrun.cpp:85:23:   required from here
speedrun.cpp:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for (int j = 0; j < ad[i].size(); j++){
      |                             ~~^~~~~~~~~~~~~~
speedrun.cpp:75:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for (int j = 1; 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