oj.uz

Submission #571087

# Submission time Handle Problem Language Result Execution time Memory
571087 2022-06-01T08:35:34 Z Theo830 Speedrun (RMI21_speedrun) C++17
100 / 100
 144 ms 800 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "speedrun.h"
vector<vll>adj;
ll par[1005];
ll tim = 0;
ll tin[1005] = {0};
ll arr[1005] = {0};
ll Next[1005];
void dfs(ll idx,ll p){
    par[idx] = p;
    tin[idx] = tim;
    arr[tim] = idx;
    tim++;
    for(auto x:adj[idx]){
        if(x != p){
            dfs(x,idx);
        }
    }
}
void assignHints(int subtask, int N, int A[], int B[]){
    setHintLen(20);
    adj.assign(N+5,vll());
    f(i,1,N){
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    dfs(1,0);
    f(i,1,N+1){
        Next[i] = arr[tin[i] + 1];
    }
    f(i,1,N+1){
        f(j,0,10){
            if(par[i] & (1LL<<j)){
                setHint(i,j + 1,1);
            }
            if(Next[i] & (1LL<<j)){
                setHint(i,j + 11,1);
            }
        }
    }
}
void speedrun(int subtask, int N, int start){
    ll cur = start;
    while(cur != 1){
        cur = 0;
        f(j,0,10){
            if(getHint(j + 1)){
                cur += (1LL<<j);
            }
        }
        assert(goTo(cur));
    }
    ll Next = 0;
    f(j,0,10){
        if(getHint(j + 11)){
            Next += (1LL<<j);
        }
    }
    while(Next != 0){
        if(goTo(Next)){
            cur = Next;
            Next = 0;
            f(j,0,10){
                if(getHint(j + 11)){
                    Next += (1LL<<j);
                }
            }
        }
        else{
            cur = 0;
            f(j,0,10){
                if(getHint(j + 1)){
                    cur += (1LL<<j);
                }
            }
            assert(goTo(cur));
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 704 KB Output is correct
2 Correct 144 ms 712 KB Output is correct
3 Correct 109 ms 704 KB Output is correct
4 Correct 137 ms 700 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 688 KB Output is correct
2 Correct 111 ms 684 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 800 KB Output is correct
2 Correct 95 ms 724 KB Output is correct
3 Correct 103 ms 800 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 672 KB Output is correct
2 Correct 97 ms 672 KB Output is correct
3 Correct 104 ms 672 KB Output is correct
4 Correct 105 ms 680 KB Output is correct
5 Correct 98 ms 688 KB Output is correct
6 Correct 123 ms 712 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 700 KB Output is correct
2 Correct 116 ms 692 KB Output is correct
3 Correct 103 ms 688 KB Output is correct
4 Correct 82 ms 676 KB Output is correct
5 Correct 129 ms 740 KB Output is correct
6 Correct 130 ms 676 KB Output is correct
7 Correct 105 ms 704 KB Output is correct