제출 #991849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991849		De3b0o	Speedrun (RMI21_speedrun)	C++14	63 / 100	105 ms	1940 KiB

speedrun

#include "speedrun.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*n)
#define rc (2*n+1)

using namespace std;

const ll NN = 1009;

ll n;
ll p[NN];
vector<ll> adj[NN];
vector<ll> df;
ll ti[NN] , to[NN];
ll t;

void dfs(ll x , ll pr)
{
    p[x]=pr;
    df.pb(x);
    ti[x]=t;
    t++;
    for(auto it : adj[x])
    {
        if(it==pr)
            continue;
        dfs(it,x);
    }
    df.pb(x);
    to[x]=t;
    t++;
}

void assignHints(int subtask, int N, int A[], int B[])
{
    setHintLen(30);
    n=N;
    for(int i = 1 ; n>i ; i++)
    {
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    dfs(1,0);
    df.pb(0);
    for(int i = 1 ; n>=i ; i++)
    {
        ll b = 1;
        for(int j = 1 ; 10>=j ; j++)
        {
            if(b&p[i])
                setHint(i,j,1);
            b*=2;
        }
        b=1;
        for(int j = 11 ; 20>=j ; j++)
        {
            if(b&df[ti[i]+1])
                setHint(i,j,1);
            b*=2;
        }
        b=1;
        for(int j = 21 ; 30>=j ; j++)
        {
            if(b&df[to[i]+1])
                setHint(i,j,1);
            b*=2;
        }
    }
}

void v(ll x , ll d , bool l)
{
    ll pr = 0;
    ll b = 1;
    for(int j = 1 ; 10>=j ; j++)
    {
        if(getHint(j))
            pr+=b;
        b*=2;
    }
    if(d)
    {
        goTo(d);
        v(d,0,1);
        return;
    }
    b=1;
    ll t1 = 0;
    for(int j = 11 ; 20>=j ; j++)
    {
        if(getHint(j))
            t1+=b;
        b*=2;
    }
    b=1;
    ll t2 = 0;
    for(int j = 21 ; 30>=j ; j++)
    {
        if(getHint(j))
            t2+=b;
        b*=2;
    }
    while(l)
    {
        if(t1==x)
        {
            l=0;
            break;
        }
        goTo(t1);
        v(t1,0,1);
        break;
    }
    while(!l)
    {
        if(x==1)
            return;
        if(t2!=pr)
        {
            goTo(pr);
            v(pr,t2,0);
        }
        else
        {
            goTo(pr);
            v(pr,0,0);
        }
        break;
    }
}

void speedrun(int subtask, int N, int start)
{
    while(true)
    {
        ll b = 1;
        ll y = 0;
        for(int j = 1 ; 10>=j ; j++)
        {
            if(getHint(j))
                y+=b;
            b*=2;
        }
        if(y==0)
            break;
        goTo(y);
    }
    v(1,0,1);
}

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