Submission #770786

#	Time	Username	Problem	Language	Result	Execution time	Memory
770786		gg123_pe	Speedrun (RMI21_speedrun)	C++14	90 / 100	144 ms	968 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[]) { 
    n = Ni; 
    f(i,1,n){
        adj[A[i]].push_back(B[i]); 
        adj[B[i]].push_back(A[i]); 
    }

    if(subtask == 2){
        setHintLen(1); 
        f(i,1,n+1){
            if(adj[i].size() == n-1){
                setHint(i, 1, 1); 
                break; 
            }
        }
        return; 
    }
    if(subtask == 3){
        setHintLen(20); 
        int l; 
        f(i,1,n+1){
            if(adj[i].size() == 1){
                l = i; 
                break; 
            }
        }
        dfs(l, 0); 
        f(i,0,n){
            int node = order[i]; 
            if(i > 0) assign(node, 1, order[i-1]); 
            if(i+1 < n) assign(node, 2, order[i+1]); 
        }
        return; 
    }
    setHintLen(30);
    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; 

    if(subtask == 2){
        int root = start; 
        if(!getHint(1)){
            f(i,1,n+1){
                if(i != start and goTo(i)){
                    root = i; 
                    break; 
                }
            }
        }
        f(i,1,n+1){
            if(i != root){
                goTo(i); 
                goTo(root);
            }
        }
        return; 
    }
    if(subtask == 3){
        while(1){
            int r = get(2); 
            if(r == 0) break; 
            start = r; 
            goTo(start); 
        }
        while(1){
            int l = get(1); 
            if(l == 0) break; 
            start = l; 
            goTo(start); 
        }
        return; 
    }
    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++; 
    }
}

Compilation message (stderr)

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:49:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |             if(adj[i].size() == n-1){
      |                ~~~~~~~~~~~~~~^~~~~~
speedrun.cpp:65:12: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |         dfs(l, 0);
      |         ~~~^~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 30 / 40