oj.uz

Submission #1019888

# Submission time Handle Problem Language Result Execution time Memory
1019888 2024-07-11T10:15:34 Z groshi Speedrun (RMI21_speedrun) C++17
100 / 100
 141 ms 1364 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 118 ms 908 KB Output is correct
2 Correct 130 ms 1112 KB Output is correct
3 Correct 123 ms 1364 KB Output is correct
4 Correct 110 ms 740 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 688 KB Output is correct
2 Correct 110 ms 936 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 1200 KB Output is correct
2 Correct 132 ms 912 KB Output is correct
3 Correct 124 ms 988 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 852 KB Output is correct
2 Correct 141 ms 688 KB Output is correct
3 Correct 137 ms 700 KB Output is correct
4 Correct 115 ms 696 KB Output is correct
5 Correct 126 ms 700 KB Output is correct
6 Correct 114 ms 740 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 856 KB Output is correct
2 Correct 122 ms 688 KB Output is correct
3 Correct 107 ms 684 KB Output is correct
4 Correct 125 ms 684 KB Output is correct
5 Correct 121 ms 736 KB Output is correct
6 Correct 126 ms 988 KB Output is correct
7 Correct 108 ms 940 KB Output is correct