oj.uz

Submission #970232

# Submission time Handle Problem Language Result Execution time Memory
970232 2024-04-26T08:46:15 Z bachhoangxuan Speedrun (RMI21_speedrun) C++17
100 / 100
 143 ms 1892 KB 
#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1005;
const int L = 20;
const int D = 1024;
int mask[maxn];
vector<int> edge[maxn];

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    for(int i=1;i<N;i++){
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
    }
    function<void(int,int)> dfs = [&](int u,int p){
        int cc=0;
        for(int v:edge[u]){
            if(v==p) continue;
            dfs(v,u);
            if(cc) mask[cc]+=v*D;
            else mask[u]+=v;
            cc=v;
        }
        if(cc) mask[cc]+=p*D;
    };
    dfs(1,0);
    setHintLen(L);
    for(int i=1;i<=N;i++){
        for(int j=0;j<L;j++) setHint(i,j+1,mask[i]>>j&1);
    }
}

bool vis[maxn];

void speedrun(int subtask, int N, int start) { /* your solution here */
    int cnt=0;
    for(int i=1;i<=N;i++) mask[i]=0;
    function<void(int)> dfs = [&](int u){
        //cout << u << '\n';
        if(vis[u]) return;
        vis[u]=true;cnt++;
        for(int j=0;j<L;j++) mask[u]|=(getHint(j+1)<<j);
        int v=mask[u]%D;
        if(!v && u==start){
            for(int i=1;i<=N;i++) if(goTo(i)){
                dfs(i);goTo(u);
                break;
            }
        }
        while(v && cnt<N){
            if(!goTo(v)) break;
            dfs(v);goTo(u);
            v=mask[v]/D;
        }
    };
    dfs(start);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1456 KB Output is correct
2 Correct 143 ms 1196 KB Output is correct
3 Correct 113 ms 1724 KB Output is correct
4 Correct 117 ms 940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 688 KB Output is correct
2 Correct 113 ms 1212 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 1196 KB Output is correct
2 Correct 128 ms 1096 KB Output is correct
3 Correct 96 ms 1892 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 1200 KB Output is correct
2 Correct 129 ms 964 KB Output is correct
3 Correct 97 ms 1360 KB Output is correct
4 Correct 108 ms 1720 KB Output is correct
5 Correct 123 ms 1452 KB Output is correct
6 Correct 94 ms 1196 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 1452 KB Output is correct
2 Correct 119 ms 1092 KB Output is correct
3 Correct 118 ms 1196 KB Output is correct
4 Correct 100 ms 1220 KB Output is correct
5 Correct 97 ms 940 KB Output is correct
6 Correct 99 ms 1208 KB Output is correct
7 Correct 111 ms 1200 KB Output is correct