Submission #647009

#	Time	Username	Problem	Language	Result	Execution time	Memory
647009		ksu2009en	Speedrun (RMI21_speedrun)	C++17	60 / 100	327 ms	820 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 long long ll;


vector<ll>d[1007];

void assignHints(int subtask, int n, int a[], int b[]) { /* your solution here */
    if(subtask == 1){
        setHintLen(n);
        for(int i = 1; i < n; i++){
            setHint(a[i], b[i], 1);
            setHint(b[i], a[i], 1);
        }
    }
    else if(subtask == 2){
        int center = 0;
        map<int, int> mp;
        for(int i = 1; i < n; i++)
            mp[a[i]]++, mp[b[i]]++;
        
        int mx = 0;
        for(auto i: mp)
            if(i.second > mx){
                mx = i.second;
                center = i.first;
            }
        
        setHintLen(20);
 
        for(int i = 1; i <= n; i++){
            if(i == center)
                continue;
            
            for(int j = 0; j < 20; j++){
                if((center >> j) % 2 != 0){
                    setHint(i, j + 1, 1);
                }
            }
        }
        
    }
    else if(subtask == 3){
        setHintLen(20);
        
        for(int i = 1; i <= n; i++){
            vector<int>nodes;
            for(int j = 1; j < n; j++){
                if(a[j] == i || b[j] == i){
                    int other = 0;
                    if(a[j] == i)
                        other = b[j];
                    else
                        other = a[j];
                    
                    nodes.push_back(other);
                }
            }
            if(!nodes.empty())
                for(int j = 0; j < 10; j++)
                    if((nodes[0] >> j) % 2 != 0)
                        setHint(i, j + 1, 1);
            
            if(nodes.size() >= 2){
                for(int j = 10; j < 20; j++)
                    if((nodes[1] >> (j - 10)) % 2 != 0)
                        setHint(i, j + 1, 1);
            }
            
        }
    }
    else if(subtask == 4){
        for(int i = 1; i < n; i++){
            d[a[i]].push_back(b[i]);
            d[b[i]].push_back(a[i]);
        }
        
        setHintLen(316);
        
        int sz = sqrt(n);
        
        for(int i = 1; i <= n; i++){
            if(d[i].size() <= sz){ // the degree is less/equal than sqrt(n) => we can build an adjestancy list (10 bits per vertex)
                int pos = 1;
                
                for(auto x: d[i]){
                    for(int j = pos; j <= pos + 9; j++){
                        if((x >> (j - pos)) % 2 != 0)
                            setHint(i, j, 1);
                    }
                    pos += 10;
                }
            }
            // else: leave it as it is, we're gonna check all N nodes using goTo later in speedrun
        }
    }
}

bool used[1007];

void dfs(int v, int par, int &n){
    used[v] = true;
    for(int i = 1; i <= n; i++){
        if(!used[i] && getHint(i)){
            goTo(i);
            dfs(i, v, n);
        }
    }
    if(par != -1)
        goTo(par);
}
 
void dfs_3(int v, int par){
    //cout << v << endl;
    used[v] = true;
    
    int v1 = 0, v2 = 0;
    for(int i = 9; i >= 0; i--){
        v1 *= 2;
        if(getHint(i + 1))
            v1++;
    }
    
    for(int i = 19; i >= 10; i--){
        v2 *= 2;
        if(getHint(i + 1))
            v2++;
    }
    
    //cout << v1 << ' ' << v2 << endl;
    
    if(!used[v1] && v1 != 0){
        goTo(v1);
        dfs_3(v1, v);
    }
    if(!used[v2] && v2 != 0){
        goTo(v2);
        dfs_3(v2, v);
    }
    if(par != -1)
        goTo(par);
}
 

void dfs_4(ll v, ll par, int &n){
    used[v] = true;
    bool ok = false;
    
    for(int i = 1; i <= 316; i++){
        if(getHint(i))
            ok = true;
    }
    
    if(!ok){ // there are no set bits, thus this node has degree > sqrt(n) and we can traverse over all N nodes using goTo (the amount of such nodes will not exceed sqrt(N) - why? idk, just seems logical, search for proof)
        
        for(int i = 1; i <= n; i++){
            if(goTo(i))
                dfs_4(i, v, n);
        }
    }
    else{ // this node has its adjactency list
        for(int i = 1; i + 9 <= 316; i += 10){ // the start of new code
            ll v2 = 0;
            for(int j = 9; j >= 0; j--){
                v2 *= 2;
                
                if(getHint(i + j))
                    v2++;
            }
            
            if(v2 == 0) // there is an end in the list!
                break;
            
            if(!used[v2]){
                goTo(v2);
                dfs_4(v2, v, n);
            }
        }
    }
    
    if(par != -1) // go back, from where we've come
        goTo(par);
}

void speedrun(int subtask, int n, int start) { /* your solution here */
if(subtask == 1){
        dfs(start, -1, n);
    }
    else if(subtask == 2){
        bool ok = false;
        for(int i = 1; i <= 20; i++)
            if(getHint(i))
                ok = true;
        
        int center = 0;
        if(ok){
            for(int j = 19; j >= 0; j--){
                center *= 2;
                if(getHint(j + 1)){
                    center++;
                }
            }
            
            goTo(center);
        }
        else
            center = start;
        
        
        for(int i = 1; i <= n; i++){
            if(i != start && i != center){
                goTo(i);
                goTo(center);
            }
        }
    }
    else if(subtask == 3){
        dfs_3(start, -1);
    }
    else if(subtask == 4){
        dfs_4(start, -1, n);
    }
}

Compilation message (stderr)

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:101:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |             if(d[i].size() <= sz){ // the degree is less/equal than sqrt(n) => we can build an adjestancy list (10 bits per vertex)
      |                ~~~~~~~~~~~~^~~~~

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