oj.uz

Submission #831100

# Submission time Handle Problem Language Result Execution time Memory
831100 2023-08-19T18:00:22 Z raphaelp Speedrun (RMI21_speedrun) C++14
0 / 100
 36 ms 656 KB 
#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;
void assign(int i, int N, int slot)
{
    for (int j = 10; j > 0; j--)
    {
        setHint(i + 1, j + (10 * slot), N % 2);
        N /= 2;
    }
}
int rec(int p, int x, vector<bool> &occ, vector<vector<int>> &Tree, int last)
{
    occ[x] = 1;
    assign(p, x, 0);
    if (Tree[x].size() == 1)
    {
        assign(x, last, 0);
    }
    for (int i = 0; i < Tree[x].size(); ++i)
    {
        if (occ[Tree[x][i]])
        {
            swap(Tree[x][i], Tree[x][Tree[x].size() - 1]);
            Tree[x].pop_back();
            i--;
            continue;
        }
        if (i != 0)
        {
            assign(Tree[x][i - 1], Tree[x][i], 1);
        }
        rec(x, Tree[x][i], occ, Tree, (i == Tree[x].size() - 1 || (i == Tree[x].size() - 2 && p == Tree[x][Tree[x].size() - 1])) ? last : x);
    }
    assign(Tree[x][Tree[x].size() - 1], x, 1);
}
void assignHints(int subtask, int N, int A[], int B[])
{
    vector<vector<int>> Tree(N);
    for (int i = 1; i <= N - 1; i++)
    {
        Tree[A[i] - 1].push_back(B[i] - 1);
        Tree[B[i] - 1].push_back(A[i] - 1);
    }
    setHintLen(20);
    vector<bool> occ(N);
    rec(0, 0, occ, Tree, 0);
}
int read(int slot)
{
    int sum = 0;
    for (int i = 1; i <= 10; i++)
    {
        sum *= 2;
        sum += getHint(i + (10 * slot));
    }
    return sum;
}
void speedrun(int subtask, int N, int start)
{
    int x = start;
    deque<int> pile;
    pile.push_back(start);
    vector<int> fils(N);
    vector<int> bro(N);
    vector<int> leaf(N);
    vector<bool> failed(N, false);
    vector<bool> failed2(N, false);
    vector<bool> occ(N, 0);
    int nbvis = 0;
    bool depile = false;
    while (nbvis < N)
    {
        if (!occ[x])
        {
            bro[x] = read(1);
            fils[x] = read(0);
        }
        if (depile)
        {
            if (!occ[x])
                nbvis++;
            occ[x] = 1;
            if (pile.size() > 1)
            {
                pile.pop_back();
                leaf[pile.back()] = leaf[x];
                bro[fils[pile.back()]] = bro[x];
                x = pile.back();
                depile = false;
            }
            else
            {
                pile.pop_back();
                failed2[leaf[x]] = goTo(bro[leaf[x]] + 1);
                if (failed2[leaf[x]])
                {
                    failed2[x] = goTo(bro[x] + 1);
                    pile.push_back(bro[x]);
                    x = bro[x];
                    depile = false;
                }
                else
                {
                    x = bro[leaf[x]];
                    pile.push_back(x);
                    depile = false;
                }
            }
        }
        else
        {
            if (pile.size() > 1 && fils[x] == pile[pile.size() - 2])
            {
                leaf[x] = x;
                depile = true;
            }
            if (pile.front() == fils[x])
                pile.pop_front();
            if (occ[fils[x]])
            {
                failed2[fils[x]] = goTo(bro[fils[x]] + 1);
                if (!failed2[fils[x]])
                {
                    x = bro[fils[x]];
                    continue;
                }
                depile = true;
            }
            else
            {
                failed[x] = goTo(fils[x] + 1);
                if (!failed[x])
                {
                    pile.push_back(fils[x]);
                    x = fils[x];
                    continue;
                }
            }
        }
    }
}

Compilation message

speedrun.cpp: In function 'int rec(int, int, std::vector<bool>&, std::vector<std::vector<int> >&, int)':
speedrun.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < Tree[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~
speedrun.cpp:34:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         rec(x, Tree[x][i], occ, Tree, (i == Tree[x].size() - 1 || (i == Tree[x].size() - 2 && p == Tree[x][Tree[x].size() - 1])) ? last : x);
      |                                        ~~^~~~~~~~~~~~~~~~~~~~~
speedrun.cpp:34:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         rec(x, Tree[x][i], occ, Tree, (i == Tree[x].size() - 1 || (i == Tree[x].size() - 2 && p == Tree[x][Tree[x].size() - 1])) ? last : x);
      |                                                                    ~~^~~~~~~~~~~~~~~~~~~~~
speedrun.cpp:37:1: warning: no return statement in function returning non-void [-Wreturn-type]
   37 | }
      | ^

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -