oj.uz

Submission #499501

# Submission time Handle Problem Language Result Execution time Memory
499501 2021-12-28T14:09:56 Z andrei_boaca Speedrun (RMI21_speedrun) C++17
100 / 100
 247 ms 4672 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4516 KB Output is correct
2 Correct 247 ms 4672 KB Output is correct
3 Correct 186 ms 4548 KB Output is correct
4 Correct 180 ms 4652 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 4500 KB Output is correct
2 Correct 200 ms 4528 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 4648 KB Output is correct
2 Correct 184 ms 4628 KB Output is correct
3 Correct 191 ms 4636 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 4540 KB Output is correct
2 Correct 210 ms 4508 KB Output is correct
3 Correct 160 ms 4644 KB Output is correct
4 Correct 163 ms 4652 KB Output is correct
5 Correct 163 ms 4500 KB Output is correct
6 Correct 185 ms 4628 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 4652 KB Output is correct
2 Correct 211 ms 4544 KB Output is correct
3 Correct 183 ms 4520 KB Output is correct
4 Correct 155 ms 4652 KB Output is correct
5 Correct 175 ms 4572 KB Output is correct
6 Correct 183 ms 4508 KB Output is correct
7 Correct 187 ms 4508 KB Output is correct