oj.uz

Submission #833397

# Submission time Handle Problem Language Result Execution time Memory
833397 2023-08-22T05:19:29 Z RaulAndrei01 Speedrun (RMI21_speedrun) C++17
100 / 100
 174 ms 852 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
#include <vector>
#include <stack>

using namespace std;
const int NMAX = 1001;
vector<int> adj[NMAX];
stack<int> ord;

void setPar (int nod , int par)
{
    int bit = 1;
    while (par)
    {
        setHint(nod , bit , par&1);
        bit++;
        par /= 2;
    }
}

void setNext (int nod , int nxt)
{
    int bit = 11;
    while (nxt)
    {
        setHint(nod , bit , nxt&1);
        bit++;
        nxt /= 2;
    }
}

void dfs (int nod = 1 , int par = 0)
{
    ord.push(nod);
    for (auto& to : adj[nod])
    {
        if (to == par) continue;
        setPar(to , nod);
        dfs(to , nod);
    }
}

void assignHints(int subtask, int N, int A[], int B[])
{
    setHintLen(20);
    for (int i = 1; i < N; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    dfs();
    int prev = 1;
    while (ord.size())
    {
        setNext(ord.top() , prev);
        prev = ord.top();
        ord.pop();
    }
}

int getPar (int nod)
{
    int par = 0;
    for (int bit = 10; bit > 0; bit--)
    {
        
        par = (par << 1) + getHint(bit);
    }

    return par;
}

int getNext (int nod)
{
    int nxt = 0;
    for (int bit = 20; bit > 10; bit--)
    {
        nxt = (nxt << 1) + getHint(bit);
    }
    return nxt;
}

void speedrun(int subtask, int N, int start)
{
    vector<bool> viz(N+1, 0);
    int visited = 1;
    int crt = start;
    viz[crt] = 1;
    while (visited < N)
    {
        int nxt = getNext(crt);
        while (goTo(nxt) == 0)
        {
            int par = getPar(crt);
            goTo(par);
            crt = par;
        }
        crt = nxt;
        visited++;
        viz[crt] = 1;
    }

}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 768 KB Output is correct
2 Correct 174 ms 760 KB Output is correct
3 Correct 174 ms 776 KB Output is correct
4 Correct 113 ms 780 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 752 KB Output is correct
2 Correct 156 ms 768 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 852 KB Output is correct
2 Correct 132 ms 788 KB Output is correct
3 Correct 105 ms 788 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 748 KB Output is correct
2 Correct 123 ms 788 KB Output is correct
3 Correct 110 ms 792 KB Output is correct
4 Correct 113 ms 780 KB Output is correct
5 Correct 149 ms 808 KB Output is correct
6 Correct 116 ms 696 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 780 KB Output is correct
2 Correct 129 ms 784 KB Output is correct
3 Correct 86 ms 760 KB Output is correct
4 Correct 165 ms 792 KB Output is correct
5 Correct 109 ms 772 KB Output is correct
6 Correct 113 ms 724 KB Output is correct
7 Correct 121 ms 724 KB Output is correct