oj.uz

Submission #498663

# Submission time Handle Problem Language Result Execution time Memory
498663 2021-12-26T04:46:57 Z model_code Speedrun (RMI21_speedrun) C++17
100 / 100
 264 ms 924 KB 
// speedrun_100_panaete.cpp
#include <bits/stdc++.h>

#include "speedrun.h"
using namespace std;
static const int N=1002;
static int n,i,j,k,p,T[N],F[N],D[N],S[N],E[2*N];
static vector<int> v[N];
static bitset<N> used;
static void dfs(int nod)
{
    E[++k]=nod;
    for(auto vec:v[nod])
        if(vec!=T[nod])
        {
            T[vec]=nod;
            dfs(vec);
            E[++k]=nod;
        }
}

/// Hint
void assignHints(int whatever,int N, int A[], int B[])
{
    n=N;T[1]=1;used[1]=1;
    setHintLen(20);
    for (int i = 1; i < n; ++i){v[A[i]].push_back(B[i]);v[B[i]].push_back(A[i]);}
    dfs(1);
    for(i=j=k=1;i<=n;i++)
    {
        while(used[E[j]])j++;
        F[k]=E[j];
        k=E[j];used[k]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=20,k=10,p=512;p;j--,k--,p>>=1)
        {
            if(p&T[i])setHint(i,j,true);else setHint(i,j,false);
            if(p&F[i])setHint(i,k,true);else setHint(i,k,false);
        }
}

///speedRun
static void ask(int nod)
{
    if(D[nod])return;
    for(j=20,k=10,p=512;p;j--,k--,p>>=1)
    {
        D[nod]=getHint(j)?D[nod]|p:D[nod];
        S[nod]=getHint(k)?S[nod]|p:S[nod];
    }
}
void speedrun(int whatever,int N, int start)
{
    int nod=start;
    while(nod>1)
    {
        ask(nod);
        nod=D[nod];
        goTo(nod);
    }
    ask(1);
    while(S[nod])
    {
        if(goTo(S[nod])){nod=S[nod];ask(nod);}
        else
        {
            int ta=D[nod];nod=S[nod];goTo(ta);
            while(!goTo(nod)){ta=D[ta];goTo(ta);}
            ask(nod);
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 744 KB Output is correct
2 Correct 221 ms 732 KB Output is correct
3 Correct 189 ms 756 KB Output is correct
4 Correct 227 ms 780 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 768 KB Output is correct
2 Correct 126 ms 716 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 760 KB Output is correct
2 Correct 114 ms 792 KB Output is correct
3 Correct 216 ms 760 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 812 KB Output is correct
2 Correct 241 ms 700 KB Output is correct
3 Correct 104 ms 752 KB Output is correct
4 Correct 106 ms 716 KB Output is correct
5 Correct 245 ms 740 KB Output is correct
6 Correct 154 ms 924 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 832 KB Output is correct
2 Correct 219 ms 744 KB Output is correct
3 Correct 189 ms 656 KB Output is correct
4 Correct 225 ms 692 KB Output is correct
5 Correct 224 ms 676 KB Output is correct
6 Correct 237 ms 704 KB Output is correct
7 Correct 184 ms 712 KB Output is correct