oj.uz

Submission #857735

# Submission time Handle Problem Language Result Execution time Memory
857735 2023-10-06T18:50:16 Z LucaLucaM Speedrun (RMI21_speedrun) C++17
100 / 100
 142 ms 2552 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 1648 KB Output is correct
2 Correct 102 ms 2412 KB Output is correct
3 Correct 112 ms 1644 KB Output is correct
4 Correct 91 ms 1408 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 1392 KB Output is correct
2 Correct 112 ms 1400 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2432 KB Output is correct
2 Correct 140 ms 1916 KB Output is correct
3 Correct 103 ms 2552 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 1516 KB Output is correct
2 Correct 111 ms 1636 KB Output is correct
3 Correct 102 ms 1404 KB Output is correct
4 Correct 142 ms 1648 KB Output is correct
5 Correct 103 ms 1544 KB Output is correct
6 Correct 119 ms 1628 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1900 KB Output is correct
2 Correct 93 ms 1648 KB Output is correct
3 Correct 99 ms 1264 KB Output is correct
4 Correct 139 ms 1408 KB Output is correct
5 Correct 97 ms 1380 KB Output is correct
6 Correct 105 ms 1644 KB Output is correct
7 Correct 102 ms 2168 KB Output is correct