Submission #1050745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050745		presko	Speedrun (RMI21_speedrun)	C++14	0 / 100	51 ms	1468 KiB

speedrun

#include<iostream>
#include<algorithm>
#include<vector>
#include "speedrun.h"
#define MAXN 2010
using namespace std;
vector<int> edges[MAXN];
void encode(int node, int code, int parent)
{
    string part1="";
    while(code>0)
    {
        bool bit=code&1;
        part1+=(char)(bit+'0');
        code>>=1;
    }
    reverse(part1.begin(),part1.end());
    while(part1.size()<10)part1='0'+part1;
    for(int i=0;i<part1.size();i++)
    {
        if(part1[i]=='1')setHint(node,i+1,1);
    }

    string part2="";
    while(parent>0)
    {
        bool bit=parent&1;
        part2+=(char)(bit+'0');
        parent>>=1;
    }
    reverse(part2.begin(),part2.end());
    while(part2.size()<10)part2='0'+part2;
    for(int i=0;i<part2.size();i++)
    {
        if(part2[i]=='1')setHint(node,i+11,1);
    }
}
pair<int,int> decode(string s)
{
    int num1=0,num2=0;
    for(int i=0;i<10;i++)
    {
        bool bit=(s[i]-'0');
        num1+=bit*(1<<(9-i));
    }
    for(int i=10;i<20;i++)
    {
        bool bit=(s[i]-'0');
        num2+=bit*(1<<(19-i));
    }
    return {num1,num2};
}
void hint(int curr, int parent, int last)
{
    if(edges[curr].size()==1 && edges[curr][0]==parent)
    {
        encode(curr,last,parent);
        return;
    }
    bool fl=1;
    for(int i=0;i<edges[curr].size();i++)
    {
        int next=edges[curr][i];
        if(next==parent)continue;
        if(fl)
        {
            encode(curr,next,parent);
            fl=0;
        }
        int last2=0;
        if(i+1<edges[curr].size())
        {
            if(edges[curr][i+1]!=parent)last2=edges[curr][i+1];
            else if(i+2<edges[curr].size())last2=edges[curr][i+2];
        }
        if(last2>0)hint(next,curr,last2);
        else hint(next,curr,last);
    }
}
void assignHints(int subtask, int N, int A[], int B[])
{
    setHintLen(20);
    for(int i=1;i<N;i++)
    {
        edges[A[i]].push_back(B[i]);
        edges[B[i]].push_back(A[i]);
    }
    for(int i=1;i<=N;i++)sort(edges[i].begin(),edges[i].end());
    hint(1,0,0);
}
int dfs(int curr)
{
    string s="";
    for(int i=1;i<=20;i++)s+=(char)(getHint(i) + '0');
    pair<int,int> data = decode(s);
    int next=data.first,parent=data.second;
    while(goTo(next))
    {
        next=dfs(next);
        goTo(curr);
        if(next==0)break;
    }
    return next;
}
void speedrun(int subtask, int N, int start)
{
    int prev=0;
    do //go to node 1
    {
        string s="";
        for(int i=1;i<=20;i++)s+=(char)(getHint(i) + '0');
        pair<int,int> data = decode(s);
        prev=data.second;
        if(prev!=0)goTo(prev);

    }while(prev!=0);

    dfs(1);
}

Compilation message (stderr)

speedrun.cpp: In function 'void encode(int, int, int)':
speedrun.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0;i<part1.size();i++)
      |                 ~^~~~~~~~~~~~~
speedrun.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<part2.size();i++)
      |                 ~^~~~~~~~~~~~~
speedrun.cpp: In function 'void hint(int, int, int)':
speedrun.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<edges[curr].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
speedrun.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if(i+1<edges[curr].size())
      |            ~~~^~~~~~~~~~~~~~~~~~~
speedrun.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             else if(i+2<edges[curr].size())last2=edges[curr][i+2];
      |                     ~~~^~~~~~~~~~~~~~~~~~~
speedrun.cpp: In function 'int dfs(int)':
speedrun.cpp:96:25: warning: unused variable 'parent' [-Wunused-variable]
   96 |     int next=data.first,parent=data.second;
      |                         ^~~~~~

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