oj.uz

Submission #499491

# Submission time Handle Problem Language Result Execution time Memory
499491 2021-12-28T14:02:48 Z andrei_boaca Speedrun (RMI21_speedrun) C++17
27 / 100
 219 ms 4644 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);
    }
    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);
    }
    else if(p!=0)
    {
        goTo(p);
        DFS(p);
    }
}
void speedrun(int subtask, int N, int start) {
    n=N;
    for(int i=1;i<=n;i++)
        use[i]=0;
    DFS(start);
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 4528 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 4560 KB Output is correct
2 Correct 219 ms 4520 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 4628 KB Output is correct
2 Correct 79 ms 4628 KB Output is correct
3 Correct 174 ms 4628 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 4512 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 4644 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -