oj.uz

Submission #573050

# Submission time Handle Problem Language Result Execution time Memory
573050 2022-06-05T16:55:54 Z urosk Speedrun (RMI21_speedrun) C++14
100 / 100
 122 ms 932 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 1005
ll n;
ll in[maxn];
vector<ll> g[maxn];
ll b[maxn];
ll nxt[maxn];
ll p[maxn];
ll ti = 1;
void dfs(ll u,ll par){
    in[u] = ti++;
    b[ti-1] = u;
    p[u] = par;
    for(ll s : g[u]){
        if(s==par) continue;
        dfs(s,u);
    }
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    n = N;
    for(ll i = 1;i<=n-1;i++){
        ll x = A[i];
        ll y = B[i];
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1,0);
    for(ll i = 1;i<=n;i++) nxt[i] = b[in[i]+1];
    for(ll i = 1;i<=n;i++){
        for(ll j = 0;j<10;j++) if(p[i]&(1<<j)) setHint(i,j+1,1);
        for(ll j = 0;j<10;j++) if(nxt[i]&(1<<j)) setHint(i,j+11,1);
    }
}
ll getpar(){
    ll y = 0;
    for(ll j = 0;j<10;j++){
        if(getHint(j+1)) y+=(1<<j);
    }
    return y;
}
ll getnxt(){
    ll y = 0;
    for(ll j = 0;j<10;j++){
        if(getHint(j+11)) y+=(1<<j);
    }
    return y;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
    ll x = start;
    ll n = N;
    ll y = x;
    while(y!=1){
        y = getpar();
        goTo(y);
        x = y;
    }
    y = getnxt();
    ll visi = 1;
    while(visi<n){
        if(goTo(y)){
            x = y;
            y = getnxt();
            visi++;
        }else{
            x = getpar();
            goTo(x);
        }
    }
    return;
}
/*
5
1 2
2 3
3 4
3 5
3
*/

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 684 KB Output is correct
2 Correct 93 ms 800 KB Output is correct
3 Correct 108 ms 672 KB Output is correct
4 Correct 111 ms 716 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 712 KB Output is correct
2 Correct 81 ms 884 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 668 KB Output is correct
2 Correct 105 ms 684 KB Output is correct
3 Correct 104 ms 932 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 840 KB Output is correct
2 Correct 122 ms 720 KB Output is correct
3 Correct 105 ms 684 KB Output is correct
4 Correct 84 ms 700 KB Output is correct
5 Correct 112 ms 712 KB Output is correct
6 Correct 103 ms 712 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 684 KB Output is correct
2 Correct 96 ms 744 KB Output is correct
3 Correct 105 ms 724 KB Output is correct
4 Correct 93 ms 684 KB Output is correct
5 Correct 104 ms 672 KB Output is correct
6 Correct 69 ms 856 KB Output is correct
7 Correct 105 ms 684 KB Output is correct