oj.uz

Submission #513589

# Submission time Handle Problem Language Result Execution time Memory
513589 2022-01-17T09:30:54 Z Alexandruabcde Speedrun (RMI21_speedrun) C++14
100 / 100
 260 ms 908 KB 
#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1005;
int L;
vector <int> G[NMAX];
int last;
void SetDad (int Node, int val) {
    for (int i = 0; i < 10; ++ i )
        setHint(Node, i+1, ((val&(1<<i)) != 0));
}

int FindDad () {
    int val = 0;
    for (int i = 10; i >= 1; -- i )
        val = val * 2 + getHint(i);

    return val;
}

void SetNextEuler (int Node, int val) {
    for (int i = 0; i < 10; ++ i )
        setHint(Node, i+11, ((val&(1<<i)) != 0));
}

int FindNextEuler () {
    int val = 0;
    for (int i = 20; i >= 11; -- i )
        val = val * 2 + getHint(i);

    return val;
}

void Dfs (int Node, int dad = 0) {
    SetDad(Node, dad);

    bool first = 1;
    for (auto it : G[Node]) {
        if (it == dad) continue;

        SetNextEuler(last, it);
        last = it;
        Dfs(it, Node);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) {
    L = 20;
    setHintLen(L);

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

    last = 1;
    Dfs(1);
}

void GoToRoot (int node) {
    while (node != 1) {
        int dad = FindDad();

        node = dad;
        goTo(dad);
    }
}

int n;
int cnt_viz;

void Solve (int node) {
    cnt_viz++;

    if (cnt_viz == n) return;

    int urm = FindNextEuler();

    while (!goTo(urm)) {
        int dad = FindDad();

        goTo(dad);
    }

    Solve(urm);
}

void speedrun(int subtask, int N, int start) {
    GoToRoot(start);

    n = N;
    cnt_viz = 0;

    Solve(1);
}

Compilation message

speedrun.cpp: In function 'void Dfs(int, int)':
speedrun.cpp:39:10: warning: unused variable 'first' [-Wunused-variable]
   39 |     bool first = 1;
      |          ^~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 704 KB Output is correct
2 Correct 224 ms 768 KB Output is correct
3 Correct 215 ms 908 KB Output is correct
4 Correct 191 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 672 KB Output is correct
2 Correct 216 ms 692 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 756 KB Output is correct
2 Correct 167 ms 752 KB Output is correct
3 Correct 135 ms 888 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 728 KB Output is correct
2 Correct 216 ms 716 KB Output is correct
3 Correct 192 ms 668 KB Output is correct
4 Correct 204 ms 748 KB Output is correct
5 Correct 178 ms 660 KB Output is correct
6 Correct 260 ms 708 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 808 KB Output is correct
2 Correct 170 ms 692 KB Output is correct
3 Correct 191 ms 804 KB Output is correct
4 Correct 217 ms 880 KB Output is correct
5 Correct 224 ms 660 KB Output is correct
6 Correct 210 ms 712 KB Output is correct
7 Correct 181 ms 660 KB Output is correct