oj.uz

Submission #1050743

# Submission time Handle Problem Language Result Execution time Memory
1050743 2024-08-09T13:49:33 Z presko Speedrun (RMI21_speedrun) C++14
0 / 100
 58 ms 1168 KB 
#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);
    }
    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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 684 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 720 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 1168 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 712 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 880 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -