Submission #859449

#	Time	Username	Problem	Language	Result	Execution time	Memory
859449		lucri	Speedrun (RMI21_speedrun)	C++17	100 / 100	120 ms	1900 KiB

speedrun

#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
void codifica(int poz,int a,int b)
{
  for(int i=10;i>=1;--i)
  {
    setHint(poz,i,a%2);
    a/=2;
  }
  for(int i=20;i>=11;--i)
  {
    setHint(poz,i,b%2);
    b/=2;
  }
}
void construieste(int nod,int uc,vector<int>a[],int t[])
{
  if(nod==1)
  {
    codifica(nod,0,a[nod][0]);
    int ant=0,ac=0;
    for(auto x:a[nod])
    {
      if(ac==0)
        ac=x;
      else
      {
        ant=ac;
        ac=x;
        construieste(ant,ac,a,t);
      }
      t[x]=nod;
    }
    construieste(ac,0,a,t);
    return;
  }
  if(a[nod].size()==1)
    codifica(nod,t[nod],uc);
  else
  {
    int ant=0,ac=0;
    if(a[nod][0]!=t[nod])
      codifica(nod,t[nod],a[nod][0]);
    else
      codifica(nod,t[nod],a[nod][1]);
    for(auto x:a[nod])
    {
      if(t[nod]==x)
        continue;
      t[x]=nod;
      if(ac==0)
        ac=x;
      else
      {
        ant=ac;
        ac=x;
        construieste(ant,ac,a,t);
      }
    }
    construieste(ac,uc,a,t);
  }
}
void assignHints(int subtask, int N, int A[], int B[])
{
  setHintLen(20);
  int n=N,t[1010];
  vector<int>a[n+5];
  t[n]=0;
  for(int i=1;i<n;++i)
  {
    t[i]=0;
    a[A[i]].push_back(B[i]);
    a[B[i]].push_back(A[i]);
  }
  construieste(1,0,a,t);
}
int decodifica1()
{
  int val=0;
  for(int i=1;i<=10;++i)
  {
    val*=2;
    val+=getHint(i);
  }
  return val;
}
int decodifica2()
{
  int val=0;
  for(int i=11;i<=20;++i)
  {
    val*=2;
    val+=getHint(i);
  }
  return val;
}
void rezolva()
{
  int nod=1,du=0;
  stack<int>s;
  s.push(1);
  while(1)
  {
    while(decodifica2()!=0&&goTo(nod=decodifica2()))
      s.push(nod);
    du=decodifica2();
    if(du==0)
      break;
    s.pop();
    goTo(s.top());
    while(goTo(du)==false)
    {
      s.pop();
      goTo(s.top());
    }
    nod=du;
    s.push(nod);
    du=0;
  }
}
void speedrun(int subtask, int N, int start)
{
  while(start!=1)
    goTo(start=decodifica1());
  rezolva();
}

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