Submission #647385

#	Time	Username	Problem	Language	Result	Execution time	Memory
647385		Niya	Speedrun (RMI21_speedrun)	C++14	0 / 100	2 ms	788 KiB

speedrun

#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;

const int maxn = 1024;
vector<int>v[maxn];
vector<int>tour;
int used[maxn];

void set_parent( int nb, int par )
{
    int cnt = 1;
    while( par != 0 )
    {
        setHint(nb,cnt,(par%2));
        par /= 2;
    }
}

void dfs( int w )
{
    used[w] = 1;
    tour.push_back(w);
    int sz = v[w].size();

    for( int i = 0; i < sz; i ++ )
    {
        int nb = v[w][i];
        if( used[nb] == 0 )
        {
            set_parent(nb,w);
            dfs(nb);
        }
    }
}

void set_next( int x, int y )
{
    int cnt = 11;
    while( y != 0 )
    {
        setHint(x,cnt,(y%2));
        y /= 2;
    }
}
void assignHints(int subtask, int N, int A[], int B[] )
{
    setHintLen(20);
    for( int i = 1; i < N; i ++ )
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }

    int sz = tour.size();
    for( int i = 0; i < sz-1; i ++ )
    {
        int x = tour[i];
        int y = tour[i+1];
        set_next(x,y);
    }
}

int parent[maxn];
int pw[maxn];

int get_parent()
{
    int x = 0;
    for( int i = 1; i <= 10; i ++ )
    {
        x += ( getHint(i) * pw[i-1] );
    }
    return x;
}

int get_next()
{
    int x = 0;
    for( int i = 11; i <= 20; i ++ )
    {
        x += ( getHint(i) * pw[i-11] );
    }
    return x;
}

void speedrun(int subtask, int N, int start)
{
   pw[0] = 1;
   for( int i = 1; i <= 10; i ++ )
    pw[i] = pw[i-1] * 2;

   int w = start;
   int cnt = 0;

   while( true )
   {

       if( cnt == N ) break;

       if( used[w] == 0 )
       {
           used[w] = 1;
           parent[w] = get_parent();
           cnt += 1;
       }

       if( cnt == N ) break;

       int next_ver = get_next();

       if( next_ver == 0 )
       {
           //if( parent[w] == 0 ) cout << 1/0 << endl;
           goTo(parent[w]);
           w = parent[w];
           continue;
       }
       else if( used[next_ver] == 1 )
       {
           //if( parent[w] == 0 ) cout << 1/0 << endl;
           goTo( parent[w]);
           w = parent[w];
           continue;
       }
       else
       {
           //if( next_ver == 0 ) cout << 1/0 << endl;
           goTo(next_ver);
           w = next_ver;
           continue;
       }
   }
}

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