oj.uz

Submission #649078

# Submission time Handle Problem Language Result Execution time Memory
649078 2022-10-09T09:03:54 Z boris_mihov Speedrun (RMI21_speedrun) C++17
100 / 100
 227 ms 840 KB 
#include "speedrun.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 1000 + 10;
const int INF  = 1e9;

int n;
int parent[MAXN];
int nextInTour[MAXN];
std::vector <int> tour;
std::vector <int> g[MAXN];

void dfs(int node, int p)
{
    parent[node] = p;
    tour.push_back(node);
    for (const int &i : g[node])
    {
        if (i == p) continue;
        dfs(i, node);
    }
}

void assignHints(int subtask, int N, int A[], int B[])
{
    n = N;
    for (int i = 1 ; i <= n-1 ; ++i)
    {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }

    dfs(1, 0);
    nextInTour[tour.back()] = 1;
    for (int i = tour.size() - 2 ; i >= 0 ; --i)
    {
        nextInTour[tour[i]] = tour[i + 1];
    }

    setHintLen(20);
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 9 ; j >= 0 ; --j)
        {
            setHint(i, 10 - j, (parent[i] & (1 << j)) > 0);
        }

        for (int j = 9 ; j >= 0 ; --j)
        {
            setHint(i, 20 - j, (nextInTour[i] & (1 << j)) > 0);
        }
    }
}

void speedrun(int subtask, int N, int start)
{
    while (start >= 2)
    {
        int par = 0, next = 0;
        for (int i = 1 ; i <= 10 ; ++i)
        {
            par *= 2;
            par += getHint(i);
        }

        for (int i = 11 ; i <= 20 ; ++i)
        {
            next *= 2;
            next += getHint(i);
        }

        goTo(par);
        start = par;
    }

    while (true)
    {
        if (start == 0) return;
        int par = 0, next = 0;
        for (int i = 1 ; i <= 10 ; ++i)
        {
            par *= 2;
            par += getHint(i);
        }

        for (int i = 11 ; i <= 20 ; ++i)
        {
            next *= 2;
            next += getHint(i);
        }

        if (next == 1) return;
        while (!goTo(next))
        {
            start = par;
            goTo(par);
            par = 0;
            for (int i = 1 ; i <= 10 ; ++i)
            {
                par *= 2;
                par += getHint(i);
            }
        }

        start = next;
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 728 KB Output is correct
2 Correct 210 ms 672 KB Output is correct
3 Correct 207 ms 724 KB Output is correct
4 Correct 227 ms 712 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 672 KB Output is correct
2 Correct 200 ms 672 KB Output is correct
3 Correct 217 ms 716 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 716 KB Output is correct
2 Correct 198 ms 672 KB Output is correct
3 Correct 176 ms 712 KB Output is correct
4 Correct 224 ms 724 KB Output is correct
5 Correct 145 ms 712 KB Output is correct
6 Correct 176 ms 676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 672 KB Output is correct
2 Correct 205 ms 672 KB Output is correct
3 Correct 206 ms 672 KB Output is correct
4 Correct 197 ms 724 KB Output is correct
5 Correct 173 ms 684 KB Output is correct
6 Correct 176 ms 672 KB Output is correct
7 Correct 209 ms 676 KB Output is correct