oj.uz

Submission #992026

# Submission time Handle Problem Language Result Execution time Memory
992026 2024-06-03T15:26:11 Z De3b0o Speedrun (RMI21_speedrun) C++14
100 / 100
 83 ms 1224 KB 
#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];
ll t;
bool g;

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);
    }
}

void assignHints(int subtask, int N, int A[], int B[])
{
    setHintLen(20);
    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;
        }
    }
}

void v(ll x , ll d)
{
    if(g)
        return;
    ll pr = 0;
    ll b = 1;
    for(int j = 1 ; 10>=j ; j++)
    {
        if(getHint(j))
            pr+=b;
        b*=2;
    }
    if(d)
    {
        if(goTo(d))
            v(d,0);
        else
        {
            goTo(pr);
            v(pr,d);
        }
    }
    b=1;
    ll t1 = 0;
    for(int j = 11 ; 20>=j ; j++)
    {
        if(getHint(j))
            t1+=b;
        b*=2;
    }
    if(t1==0)
    {
        g=1;
        return;
    }
    if(goTo(t1))
        v(t1,0);
    else
    {
        goTo(pr);
        v(pr,t1);
    }
}

void speedrun(int subtask, int N, int start)
{
    n=N;
    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);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 992 KB Output is correct
2 Correct 83 ms 1096 KB Output is correct
3 Correct 59 ms 940 KB Output is correct
4 Correct 63 ms 684 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 944 KB Output is correct
2 Correct 46 ms 956 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 944 KB Output is correct
2 Correct 51 ms 684 KB Output is correct
3 Correct 60 ms 692 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 932 KB Output is correct
2 Correct 60 ms 892 KB Output is correct
3 Correct 53 ms 904 KB Output is correct
4 Correct 46 ms 700 KB Output is correct
5 Correct 53 ms 684 KB Output is correct
6 Correct 61 ms 900 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 940 KB Output is correct
2 Correct 67 ms 920 KB Output is correct
3 Correct 58 ms 1224 KB Output is correct
4 Correct 65 ms 684 KB Output is correct
5 Correct 53 ms 1168 KB Output is correct
6 Correct 56 ms 944 KB Output is correct
7 Correct 51 ms 884 KB Output is correct