Submission #498663

#	Time	Username	Problem	Language	Result	Execution time	Memory
498663		model_code	Speedrun (RMI21_speedrun)	C++17	100 / 100	264 ms	924 KiB

speedrun

// 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 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40