Submission #1097380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097380		heeheeheehaaw	Speedrun (RMI21_speedrun)	C++17	100 / 100	139 ms	1132 KiB

speedrun

#include <bits/stdc++.h>
#include "speedrun.h"

using namespace std;

vector<int> adj[1005];
bool visited[1005];
vector<int> ord;
int parent[1005];
int vis[1005];

void dfs(int nod, int par)
{
    parent[nod] = par;
    if(!visited[nod])
        visited[nod] = true, ord.push_back(nod);
    for(auto it : adj[nod])
    {
        if(it != par)
            dfs(it, nod);
    }
}

void assignHints(int subtask, int n, int a[], int b[])
{
    setHintLen(20);
    for(int i = 1; i < n; i++)
    {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }

    dfs(1, 1);

    for(int i = 0; i < ord.size() - 1; i++)
    {
        for(int b = 0; b < 10; b++)
        {
            if(((1 << b) & (ord[i + 1])) != 0)
                setHint(ord[i], b + 1, 1);
            else
                setHint(ord[i], b + 1, 0);
        }
    }

    for(int i = 0; i < ord.size(); i++)
    {
        for(int b = 0; b < 10; b++)
        {
            if(((1 << b) & parent[ord[i]]) != 0)
                setHint(ord[i], b + 1 + 10, 1);
            else
                setHint(ord[i], b + 1 + 10, 0);
        }
    }

    for(int b = 0; b < 10; b++)
    {
        if(((1 << b) & (ord[0])) != 0)
            setHint(ord.back(), b + 1, 1);
        else
            setHint(ord.back(), b + 1, 0);
    }
}

void speedrun(int subtask, int n, int start)
{
    int curr = start, cnt = n, nxt = -1;
    while(cnt > 0)
    {
        if(vis[curr] == 0)
            cnt--, vis[curr] = 1;
        int u = 0, par = 0;
        for(int i = 1; i <= 10; i++)
            u += (1 << (i - 1)) * getHint(i);
        if(nxt != -1)
            u = nxt;
        for(int i = 11; i <= 20; i++)
            par += (1 << (i - 1 - 10)) * getHint(i);
        bool ok = goTo(u);
        if(ok == true)
        {
            curr = u;
            nxt = -1;
        }
        else
        {
            goTo(par);
            curr = par;
            nxt = u;
        }
    }

    return;
}

Compilation message (stderr)

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

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