oj.uz

Submission #857734

# Submission time Handle Problem Language Result Execution time Memory
857734 2023-10-06T18:47:25 Z LucaLucaM Speedrun (RMI21_speedrun) C++17
0 / 100
 1 ms 344 KB 
#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;

/**

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)) {
            setHint(1, j + 10, 1);
        } else {
            setHint(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)) {
                setHint(u, j, 1);
            } else {
                setHint(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)) {
                setHint(order[i - 1], j + 10, 1);
            } else {
                setHint(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 (getHint(j)) {
                ret |= (1 << j);
            }
        }
        return ret;
    };

    auto frt = [&] () -> int {
        int ret = 0;
        for (int j = 0; j < 10; j++) {
            if (getHint(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

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Invalid bit index for setHint
2 Halted 0 ms 0 KB -