oj.uz

Submission #765382

# Submission time Handle Problem Language Result Execution time Memory
765382 2023-06-24T11:54:28 Z vjudge1 Speedrun (RMI21_speedrun) C++17
100 / 100
 111 ms 960 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include "speedrun.h"

// Akhmet Issa

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e3 + 100;
const ll INF = (ll)2e18;
const int inf = (ll)2e9;
const int maxl = 20;
const int MOD = 1e9 + 7;

vector<int> g[maxn];
vector<int> ord;

void calc(int v, int pr){
    ord.push_back(v);
    for(int to: g[v]){
        if(to != pr){
            for(int j = 0; j < 10; j++){
                if(v & (1<<j)) setHint(to, j + 11, 1);
            }
            calc(to, v);
        }
    }
}

void assignHints(int subtask, int n, int A [], int B []){
    for(int i = 1; i < n; i++){
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    setHintLen(20);
    calc(1, 0);
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < 10; j++){
            if(ord[i+1] & (1<<j)) setHint(ord[i], j + 1, 1);
        }
    }
}

int get(int p){
    int ans = 0;
    for(int i = 0; i < 10; i++){
        if(getHint(p + i)) ans |= (1<<i);
    }
    return ans;
}

void dfs(int v, int to){
    if(!to) return;
    if(goTo(to)){
        int nxt = get(1);
        dfs(to, nxt);
    } else{
        int pr = get(11);
        goTo(pr);
        dfs(pr, to);
    }
}

void speedrun(int subtask, int n, int start){
    while(start != 1){
        start = get(11);
        goTo(start);
    }
    dfs(1, get(1));
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 772 KB Output is correct
2 Correct 88 ms 756 KB Output is correct
3 Correct 111 ms 708 KB Output is correct
4 Correct 64 ms 748 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 820 KB Output is correct
2 Correct 92 ms 744 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 752 KB Output is correct
2 Correct 84 ms 892 KB Output is correct
3 Correct 97 ms 796 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 784 KB Output is correct
2 Correct 59 ms 960 KB Output is correct
3 Correct 98 ms 672 KB Output is correct
4 Correct 102 ms 672 KB Output is correct
5 Correct 70 ms 772 KB Output is correct
6 Correct 97 ms 760 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 724 KB Output is correct
2 Correct 62 ms 744 KB Output is correct
3 Correct 69 ms 716 KB Output is correct
4 Correct 93 ms 724 KB Output is correct
5 Correct 96 ms 728 KB Output is correct
6 Correct 100 ms 720 KB Output is correct
7 Correct 103 ms 672 KB Output is correct