Submission #499501

#	Time	Username	Problem	Language	Result	Execution time	Memory
499501		andrei_boaca	Speedrun (RMI21_speedrun)	C++17	100 / 100	247 ms	4672 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
//#include "grader.cpp"

int muchii[1005][1005];
int st[1005],l;
int n,par[1005];
bool use[1005];
void dfs(int nod)
{
    st[l]=nod;
    l++;
    use[nod]=1;
    for(int j=1;j<=muchii[nod][0];j++)
    {
        int i=muchii[nod][j];
        if(!use[i])
        {
            par[i]=nod;
            dfs(i);
        }
    }
}
void assignHints(int subtask, int N, int A[], int B[]) {
    n=N;
    for(int i=1;i<n;i++)
    {
        muchii[A[i]][0]++;
        muchii[A[i]][muchii[A[i]][0]]=B[i];

        muchii[B[i]][0]++;
        muchii[B[i]][muchii[B[i]][0]]=A[i];
    }
    dfs(1);
    setHintLen(20);
    for(int i=0;i<n;i++)
    {
        int p=par[st[i]];
        int nod=st[i];
        int lg=0;
        for(int bit=9;bit>=0;bit--)
        {
            lg++;
            if((p>>bit)&1)
                setHint(nod,lg,1);
            else
                setHint(nod,lg,0);
        }
        int nxt=0;
        if(i+1<n)
            nxt=st[i+1];
        for(int bit=9;bit>=0;bit--)
        {
            lg++;
            if((nxt>>bit)&1)
                setHint(nod,lg,1);
            else
                setHint(nod,lg,0);
        }
    }
}
int nxt,p;
void getvals()
{
    nxt=0,p=0;
    for(int i=1;i<=10;i++)
        p=p*2+getHint(i);
    for(int i=11;i<=20;i++)
        nxt=nxt*2+getHint(i);
}
int nrused=0;
void DFS(int nod)
{
    if(use[nod]==0)
    {
        use[nod]=1;
        nrused++;
    }
    if(nrused==n)
        return;
    getvals();
    if(nxt==0&&p!=0)
    {
        goTo(p);
        DFS(p);
        return;
    }
    else if(!use[nxt])
    {
        while(!goTo(nxt)&&p!=0)
        {
            goTo(p);
            /*if(use[p]==0)
            {
                use[p]=1;
                nrused++;
            }
            if(nrused==n)
                return;*/
            int aux=nxt;
            getvals();
            nxt=aux;
        }
        DFS(nxt);
        return;
    }
    else if(p!=0)
    {
        goTo(p);
        DFS(p);
        return;
    }

}
void speedrun(int subtask, int N, int start) {
    n=N;
    for(int i=1;i<=n;i++)
        use[i]=0;
    DFS(start);
}

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40