oj.uz

Submission #770784

# Submission time Handle Problem Language Result Execution time Memory
770784 2023-07-01T23:47:48 Z gg123_pe Speedrun (RMI21_speedrun) C++14
63 / 100
 150 ms 804 KB 
#include "speedrun.h"
#include <bits/stdc++.h> 

using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1005; 

void setHintLen (int l);
void setHint(int i, int j, bool b);
int getLength ();
bool getHint(int j);
bool goTo(int x);

int n; 
int p[N]; 
vector <int> adj[N], curr, order; 
bool vis[N]; 

void dfs(int u, int f){
    curr.push_back(u);
    order.push_back(u); 

    p[u] = f; 

    for(int v: adj[u]){
        if(v == f) continue; 
        dfs(v, u); 
    }
    if(f != 0) curr.push_back(f); 
}
void assign(int node, int pos, int val){
    int l = 10*(pos-1) + 1, r = 10*pos;
    f(i,l,r+1){
        int x = i - l; 
        if(val&(1<<x)) setHint(node, i, 1);
    } 
}
void assignHints(int subtask, int Ni, int A[], int B[]) { 
    setHintLen(30); 
    n = Ni; 
    f(i,1,n){
        adj[A[i]].push_back(B[i]); 
        adj[B[i]].push_back(A[i]); 
    }
    dfs(1, 0); 
    
    int id = 0; 
    f(i,0,n){
        int node = order[i]; 
        assign(node, 1, p[node]); 
        assign(node, 2, curr[id++]);
        assign(node, 3, curr[id++]);   
    }
}
int get(int pos){
    int ans = 0, l = 10*(pos-1) + 1, r = 10*pos;
    f(i,l,r+1){
        int x = i-l; 
        if(getHint(i)) ans ^= (1<<x); 
    }
    return ans; 
}
void speedrun(int subtask, int Ni, int start) { 
    n = Ni; 
    while(start != 1) {
        start = get(1); 
        goTo(start); 
    }
     
    if(get(2) != 0) curr.push_back(get(2));
    if(get(3) != 0) curr.push_back(get(3));   
    int id = 1; 
    vis[1] = 1;  

    while(id < (int) curr.size()){
        int node = curr[id]; 
        if(!goTo(node))
            return; 
        
        if(!vis[node]){
            vis[node] = 1; 
            if(get(2) != 0) curr.push_back(get(2));
            if(get(3) != 0) curr.push_back(get(3));   
        }
        id++; 
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 752 KB Output is correct
2 Correct 87 ms 672 KB Output is correct
3 Correct 61 ms 768 KB Output is correct
4 Correct 109 ms 692 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 788 KB Output is correct
2 Correct 142 ms 720 KB Output is correct
3 Correct 109 ms 772 KB Output is correct
4 Correct 103 ms 804 KB Output is correct
5 Correct 126 ms 688 KB Output is correct
6 Correct 111 ms 752 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 140 ms 748 KB Partial solution
2 Partially correct 117 ms 760 KB Partial solution
3 Partially correct 74 ms 776 KB Partial solution
4 Partially correct 141 ms 712 KB Partial solution
5 Partially correct 150 ms 788 KB Partial solution
6 Partially correct 103 ms 752 KB Partial solution
7 Partially correct 65 ms 788 KB Partial solution