oj.uz

Submission #1118842

# Submission time Handle Problem Language Result Execution time Memory
1118842 2024-11-26T08:48:32 Z MateiKing80 Speedrun (RMI21_speedrun) C++14
100 / 100
 236 ms 2184 KB 
#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

/*
void setHintLen (int l);
void setHint(int i, int j, bool b);
int getLength ();
bool getHint(int j);
bool goTo(int x);

intr-un nod ne tinem 2 lucruri: cel mai din stanga fiu si urmatorul fiu mai la dreapta
al tatalui nodului
*/

vector<int> vec[1005];
vector<int> fii[1005];


void bagaHint(int nod, int val)
{
    for(int i = 1; i <= 20; i ++)
        if(val & (1 << (i - 1)))
            setHint(nod, i, 1);
}

void dfsHint(int nod, int papa, int fiuDrPapa)
{
    for(auto i : vec[nod])
    {
        if(i == papa)
            continue;
        fii[nod].push_back(i);
    }
    bagaHint(nod, fiuDrPapa);
    if(fii[nod].empty())
        return;
    bagaHint(nod, (1 << 10) * fii[nod][0]);
    int fprec = papa;
    for(int i = fii[nod].size() - 1; i >= 0; i --)
    {
        dfsHint(fii[nod][i], nod, fprec);
        fprec = fii[nod][i];
    }
}

void assignHints(int subtask, int n, int A[], int B[])
{
    setHintLen(20);
    for(int i = 1; i < n; i ++)
        vec[A[i]].push_back(B[i]),
        vec[B[i]].push_back(A[i]);
    dfsHint(1, 0, 0);
}

int nextdr()
{
    int ans = 0;
    for(int i = 1; i <= 10; i ++)
        if(getHint(i))
            ans += (1 << (i - 1));
    return ans;
}

int fiust()
{
    int ans = 0;
    for(int i = 1; i <= 10; i ++)
        if(getHint(i + 10))
            ans += (1 << (i - 1));
    return ans;
}


void dfs(int nod, int papa)
{
    if(fiust() == 0)
        return;
    auto x = fiust();
    while(x != papa)
    {
        goTo(x);
        dfs(x, nod);
        x = nextdr();
        goTo(nod);
        if(x != papa)
            goTo(x);
    }
}

void speedrun(int subtask, int n, int start)
{
    if(n == 1)
        return;
    int nod = start;
    while(1)
    {
        int x = fiust();
        if(x == 0)
            break;
        goTo(x);
        nod = x;
    }
    int papa = -1;
    for(int i = 1; i <= n; i ++)
        if(i != nod && goTo(i))
        {
            papa = i;
            break;
        }
    goTo(nod);
    while(nod != 1)
    {
        int nxt = nextdr();
        goTo(papa);
        if(papa == 1)
            break;
        if(nxt == 0 || !goTo(nxt))
            swap(nod, papa);
        else
            nod = nxt;
    }
    dfs(1, 0);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 1616 KB Output is correct
2 Correct 169 ms 1920 KB Output is correct
3 Correct 188 ms 1356 KB Output is correct
4 Correct 167 ms 1396 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 924 KB Output is correct
2 Correct 123 ms 1108 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 1668 KB Output is correct
2 Correct 214 ms 1628 KB Output is correct
3 Correct 236 ms 2184 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 1856 KB Output is correct
2 Correct 177 ms 1168 KB Output is correct
3 Correct 140 ms 1356 KB Output is correct
4 Correct 182 ms 1176 KB Output is correct
5 Correct 184 ms 1364 KB Output is correct
6 Correct 156 ms 1120 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 1864 KB Output is correct
2 Correct 147 ms 1348 KB Output is correct
3 Correct 118 ms 1120 KB Output is correct
4 Correct 153 ms 1392 KB Output is correct
5 Correct 136 ms 1368 KB Output is correct
6 Correct 166 ms 1584 KB Output is correct
7 Correct 155 ms 1384 KB Output is correct