oj.uz

Submission #643131

# Submission time Handle Problem Language Result Execution time Memory
643131 2022-09-21T09:16:32 Z Tenis0206 Speedrun (RMI21_speedrun) C++17
100 / 100
 219 ms 940 KB 
/**
* user:  arsenoiu-d07
* fname: Iulian George
* lname: Arsenoiu
* task:  Speedrun
* score: 100.0
* date:  2021-12-16 07:52:56.589066
*/
#include <bits/stdc++.h>
#include "speedrun.h"

using namespace std;

vector<int> G[1005];

int t[1005],l[1005];
int cnt = 0;


/// testing part

/*int hint[1005][1005];
int current_node = 0;

int ad[1005][1005];

int A[1005],B[1005];

void setHintLen(int val)
{
    return;
}

int getLength()
{
    int nu_a_intrebat_nimeni;
    return nu_a_intrebat_nimeni;
}

void setHint(int i, int j, int b)
{
    hint[i][j] = b;
}

int getHint(int j)
{
    return hint[current_node][j];
}

bool goTo(int nod)
{
    if(ad[current_node][nod])
    {
        current_node = nod;
        return true;
    }
    return false;
}
*/

///end of testing part

void dfs_set(int nod, int dad = 0)
{
    t[nod] = dad;
    l[++cnt] = nod;
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        dfs_set(it,nod);
    }
}

void set_dad(int nod, int dad)
{
    for(int j=0;j<10;j++)
    {
        setHint(nod,j+1,((dad&(1<<j))!=0));
    }
}

void set_next(int nod, int val)
{
    for(int j=0;j<10;j++)
    {
        setHint(nod,j+11,((val&(1<<j))!=0));
    }
}

void assignHints(int subtask, int n, int a[], int b[])
{
    for(int i=1;i<n;i++)
    {
        int x = a[i];
        int y = b[i];
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs_set(1);
    setHintLen(20);
    for(int i=1;i<=n;i++)
    {
        set_dad(i,t[i]);
    }
    for(int i=1;i<=n;i++)
    {
        set_next(l[i],l[i+1]);
    }
}

int get_dad()
{
    int dad = 0;
    for(int j=0;j<10;j++)
    {
        int b = getHint(j+1);
        if(b)
        {
            dad+=(1<<j);
        }
    }
    return dad;
}

int get_next()
{
    int u = 0;
    for(int j=0;j<10;j++)
    {
        int b = getHint(j+11);
        if(b)
        {
            u+=(1<<j);
        }
    }
    return u;
}

void speedrun(int subtask, int n, int start)
{
    int nod = start;
    getLength();
    while(nod!=1)
    {
        int t = get_dad();
        goTo(t);
        nod = t;
    }
    for(int i=1;i<n;i++)
    {
        int u = get_next();
        bool done = false;
        while(!done)
        {
            bool ok = goTo(u);
            if(ok)
            {
                break;
            }
            int t = get_dad();
            goTo(t);
        }
        //cerr<<current_node<<' ';
    }
}

/*int main()
{
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>A[i]>>B[i];
        ad[A[i]][B[i]] = ad[B[i]][A[i]] = true;
    }
    assignHints(0,n,A,B);
    int start;
    cin>>start;
    current_node = start;
    speedrun(0,n,start);
    return 0;
}
*/

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 676 KB Output is correct
2 Correct 193 ms 728 KB Output is correct
3 Correct 192 ms 752 KB Output is correct
4 Correct 190 ms 940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 672 KB Output is correct
2 Correct 134 ms 672 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 684 KB Output is correct
2 Correct 178 ms 696 KB Output is correct
3 Correct 185 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 676 KB Output is correct
2 Correct 114 ms 716 KB Output is correct
3 Correct 142 ms 712 KB Output is correct
4 Correct 185 ms 728 KB Output is correct
5 Correct 212 ms 732 KB Output is correct
6 Correct 163 ms 724 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 672 KB Output is correct
2 Correct 205 ms 672 KB Output is correct
3 Correct 147 ms 728 KB Output is correct
4 Correct 199 ms 676 KB Output is correct
5 Correct 199 ms 716 KB Output is correct
6 Correct 167 ms 756 KB Output is correct
7 Correct 213 ms 716 KB Output is correct