Submission #857735

#	Time	Username	Problem	Language	Result	Execution time	Memory
857735		LucaLucaM	Speedrun (RMI21_speedrun)	C++17	100 / 100	142 ms	2552 KiB

speedrun

#warning Mom, I'm MateiKing80

#ifndef SPEEDRUN_H_INCLUDED
#define SPEEDRUN_H_INCLUDED

#ifndef LOCAL

#include "speedrun.h"

#endif

#ifdef LOCAL
void assignHints(int subtask, int N, int A[], int B[]);
void speedrun(int subtask, int N, int start);

void setHintLen(int l);
void setHint(int i, int j, bool b);
int getLength();
bool getHint(int j);
bool goTo(int x);
#endif

#include <bits/stdc++.h>

using namespace std;

void susHint (int i, int j, bool b) {
    setHint(i, j + 1, b);
}
bool getSusHint (int j) {
    return getHint(j + 1);
}

/**

primii 10 biti sunt parintele si ultimii 10 biti sunt fratele

**/

void assignHints(int subtask, int n, int A[], int B[]) { /* your solution here */
    vector<int> g[n + 1];

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

    setHintLen(20);

    int amongus = g[1][0];
    for (int j = 0; j < 10; j++) {
        if (amongus & (1 << j)) {
            susHint(1, j + 10, 1);
        } else {
            susHint(1, j + 10, 0);
        }
    }

    vector<int>order;

    function<void(int, int)> dfs = [&] (int u, int p = 0) {
        for (int j = 0; j < 10; j++) {
            if (p & (1 << j)) {
                susHint(u, j, 1);
            } else {
                susHint(u, j, 0);
            }
        }
        order.push_back(u);
        for (const auto &v : g[u]) {
            if (v != p) {
                dfs(v, u);
            }
        }
    };

    dfs(1, 0);

    order.push_back(0);

    for (int i = 1; i < (int) order.size(); i++) {
        for (int j = 0; j < 10; j++) {
            if (order[i] & (1 << j)) {
                susHint(order[i - 1], j + 10, 1);
            } else {
                susHint(order[i - 1], j + 10, 0);
            }
        }
    }
}

void speedrun(int subtask, int n, int u) {
    auto parent = [&] () -> int {
        int ret = 0;
        for (int j = 0; j < 10; j++) {
            if (getSusHint(j)) {
                ret |= (1 << j);
            }
        }
        return ret;
    };

    auto frt = [&] () -> int {
        int ret = 0;
        for (int j = 0; j < 10; j++) {
            if (getSusHint(j + 10)) {
                ret |= (1 << j);
            }
        }
        return ret;
    };

    while (parent() != 0) {
        u = parent();
        assert(goTo(parent()));
    }

    bool vis[n + 1] = {};

    while (true) {
//        cout << " > " << u << '\n';
        vis[u] = true;
        if (count(vis + 1, vis + n + 1, true) == n) {
            break;
        }
        int next = frt();
        while (!goTo(next)) {
            u = parent();
            goTo(parent());
        }
        u = next;
    }
}


#endif // SPEEDRUN_H_INCLUDED

Compilation message (stderr)

speedrun.cpp:1:16: warning: missing terminating ' character
    1 | #warning Mom, I'm MateiKing80
      |                ^
speedrun.cpp:1:2: warning: #warning Mom, I'm MateiKing80 [-Wcpp]
    1 | #warning Mom, I'm MateiKing80
      |  ^~~~~~~

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