oj.uz

Submission #859449

# Submission time Handle Problem Language Result Execution time Memory
859449 2023-10-10T07:28:21 Z lucri Speedrun (RMI21_speedrun) C++17
100 / 100
 120 ms 1900 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1604 KB Output is correct
2 Correct 102 ms 1344 KB Output is correct
3 Correct 104 ms 1596 KB Output is correct
4 Correct 98 ms 1900 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1600 KB Output is correct
2 Correct 115 ms 1600 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 1356 KB Output is correct
2 Correct 95 ms 1088 KB Output is correct
3 Correct 113 ms 1592 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 1356 KB Output is correct
2 Correct 107 ms 960 KB Output is correct
3 Correct 98 ms 1348 KB Output is correct
4 Correct 106 ms 824 KB Output is correct
5 Correct 114 ms 1344 KB Output is correct
6 Correct 106 ms 1340 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1732 KB Output is correct
2 Correct 102 ms 1332 KB Output is correct
3 Correct 98 ms 1464 KB Output is correct
4 Correct 104 ms 1092 KB Output is correct
5 Correct 114 ms 1100 KB Output is correct
6 Correct 120 ms 1596 KB Output is correct
7 Correct 103 ms 1216 KB Output is correct