Submission #647021

#	Time	Username	Problem	Language	Result	Execution time	Memory
647021		ksu2009en	Speedrun (RMI21_speedrun)	C++17	100 / 100	135 ms	920 KiB

speedrun

#include "speedrun.h"

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef int ll;

vector<ll>d[1007];

vector<ll>list;

ll parent[1007];

void dfs(ll v, ll par){
    list.push_back(v);
    
    if(par != -1)
        parent[v] = par;
    
    for(auto i: d[v])
        if(i != par)
            dfs(i, v);
}

void assignHints(int subtask, int n, int a[], int b[]) { /* your solution here */
    for(int i = 1; i < n; i++){
        d[a[i]].push_back(b[i]);
        d[b[i]].push_back(a[i]);
    }
    
    ll root = 0;
    for(int i = 1; i <= n; i++)
        if(d[i].size() == 1){
            root = i;
            parent[root] = d[i][0];
            break;
        }
    
    dfs(root, -1);
    
    setHintLen(20);
    
    for(int i = 0; i < list.size(); i++){
        for(int j = 0; j < 10; j++)
            if((parent[list[i]] >> j) % 2 != 0)
                setHint(list[i], j + 1, 1);
        
        ll next = (i + 1 < list.size() ? list[i + 1] : list[0]);
        
        for(int j = 0; j < 10; j++)
            if((next >> j) % 2 != 0)
                setHint(list[i], j + 1 + 10, 1);
    }
}

bool used[1007];

void speedrun(int subtask, int n, int start) { /* your solution here */
    ll visited = 1;
    used[start] = true;
    
    ll go_here = -1, v = start;
    
    while(visited < n){
        //cout << v << endl;
        used[v] = true;
        ll next = 0;
        
        for(int i = 9; i >= 0; i--){
            next *= 2;
            if(getHint(20 - (10 - i - 1)))
                next++;
        }
        
        ll father = 0;
        
        for(int i = 9; i >= 0; i--){
            father *= 2;
            if(getHint(i + 1))
                father++;
        }
        
        //cout << next << ' ' << father << ' ' << go_here<< endl;
        
        if(go_here != -1){
            if(goTo(go_here)){
                v = go_here;
                
                if(!used[go_here])
                    visited++;
                go_here = -1;
            }
            else{
                goTo(father);
                
                v = father;
                
                if(!used[father])
                    visited++;
            }
            continue;
        }
        
        
        if(goTo(next)){
            v = next;
            go_here = -1;
            
            if(!used[next])
                visited++;
            continue;
        }
        
        go_here = next;
        goTo(father);
        
        v = father;
        
        if(!used[father])
            visited++;
    }
    
}

/*
 5
 5
 1 2
 2 3
 3 4
 3 5
 2
 */

Compilation message (stderr)

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 0; i < list.size(); i++){
      |                    ~~^~~~~~~~~~~~~
speedrun.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         ll next = (i + 1 < list.size() ? list[i + 1] : list[0]);
      |                    ~~~~~~^~~~~~~~~~~~~

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