Submission #770784

#	Time	Username	Problem	Language	Result	Execution time	Memory
770784		gg123_pe	Speedrun (RMI21_speedrun)	C++14	63 / 100	150 ms	804 KiB

speedrun

#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 / 21
• Subtask 2: 0 / 8
• Subtask 3: 0 / 19
• Subtask 4: 12 / 12
• Subtask 5: 30 / 40