oj.uz

Submission #853512

# Submission time Handle Problem Language Result Execution time Memory
853512 2023-09-24T13:23:22 Z ivaaaaaaan Speedrun (RMI21_speedrun) C++17
100 / 100
 124 ms 1876 KB 
#include <bits/stdc++.h>
#include "speedrun.h"

using namespace std;

/// de comentat
/*
string s[1001];
vector <int> mc[1001];

void setHintLen (int x)
{
    //
}

void setHint (int i, int j, int b)
{
    if (b == 1)
    {
        s[i] += '1';
    }
    else
    {
        s[i] += '0';
    }
}

bool getHint (int i, int j)
{
    if (s[i][j - 1] == '1')
    {
        return true;
    }
    return false;
}

bool goTo(int nod, int x)
{
    for (auto f : mc[nod])
    {
        if (f == x)
        {
            return true;
        }
    }
    return false;
}
*/
/// de inclus in cod

const int max_size = 1e3 + 1;

int dfstree[max_size], poz, t[max_size];
vector <int> mc[max_size];

void dfs (int nod, int par)
{
    t[nod] = par;
    dfstree[++poz] = nod;
    for (auto f : mc[nod])
    {
        if (f == par)
        {
            continue;
        }
        dfs(f, nod);
    }
}

void assignHints (int subtask, int N, int A[], int B[])
{
    setHintLen(20);
    for (int i = 1; i < N; i++)
    {
        mc[A[i]].push_back(B[i]);
        mc[B[i]].push_back(A[i]);
    }
    dfs(1, 0);
    /// primii 10 biti pentru tata, ult 10 biti pt poz
    for (int i = 1; i <= N; i++)
    {
        int x = t[i];
        for (int j = 0; j < 10; j++)
        {
            if ((x & (1 << j)) != 0)
            {
                setHint(i, j + 1, 1);
            }
            else
            {
                setHint(i, j + 1, 0);
            }
        }
    }
    for (int i = 1; i < N; i++)
    {
        int x = dfstree[i], y = dfstree[i + 1];
        for (int j = 0; j < 10; j++)
        {
            if ((y & (1 << j)) != 0)
            {
                setHint(x, 10 + j + 1, 1);
            }
            else
            {
                setHint(x, 10 + j + 1, 0);
            }
        }
    }
    int x = dfstree[N], y = dfstree[1];
    for (int j = 0; j < 10; j++)
    {
        if ((y & (1 << j)) != 0)
        {
            setHint(x, 10 + j + 1, 1);
        }
        else
        {
            setHint(x, 10 + j + 1, 0);
        }
    }
}

void speedrun (int subtask, int N, int start )
{
    int nod = start;
    for (int i = 1; i < N; i++)
    {
        int urm = 0;
        for (int j = 11; j <= 20; j++)
        {
            int x = getHint(j);
            if (x == 1)
            {
                urm += (1 << (j - 11));
            }
        }
        //cout << urm << " ";
        while (!goTo(urm))
        {
            int par = 0;
            for (int j = 1; j <= 10; j++)
            {
                int x = getHint(j);
                if (x == 1)
                {
                    par += (1 << (j - 1));
                }
            }
            bool x = goTo(par);
            nod = par;
        }
        bool x = goTo(urm);
        nod = urm;
       // cout << nod << " ";
    }
    return;
}

Compilation message

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:150:18: warning: unused variable 'x' [-Wunused-variable]
  150 |             bool x = goTo(par);
      |                  ^
speedrun.cpp:153:14: warning: unused variable 'x' [-Wunused-variable]
  153 |         bool x = goTo(urm);
      |              ^
speedrun.cpp:126:9: warning: variable 'nod' set but not used [-Wunused-but-set-variable]
  126 |     int nod = start;
      |         ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1360 KB Output is correct
2 Correct 107 ms 1868 KB Output is correct
3 Correct 97 ms 1272 KB Output is correct
4 Correct 109 ms 1616 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 1540 KB Output is correct
2 Correct 101 ms 1272 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1364 KB Output is correct
2 Correct 98 ms 1376 KB Output is correct
3 Correct 114 ms 1196 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1104 KB Output is correct
2 Correct 96 ms 1568 KB Output is correct
3 Correct 124 ms 1264 KB Output is correct
4 Correct 115 ms 1712 KB Output is correct
5 Correct 103 ms 1520 KB Output is correct
6 Correct 107 ms 1024 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 1508 KB Output is correct
2 Correct 100 ms 1276 KB Output is correct
3 Correct 99 ms 1624 KB Output is correct
4 Correct 97 ms 1104 KB Output is correct
5 Correct 92 ms 1876 KB Output is correct
6 Correct 96 ms 1364 KB Output is correct
7 Correct 89 ms 1104 KB Output is correct