///////////////////////////////////////////////////////////////////////////////////////
#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int,int>
#define vii vector<pii>
////////////////////////////////////// Part 1
/**
void setHintLen (int l);
void setHint (int i, int j, bool b);
**/
vvi conexiones;
vi padre;
vvi hijos;
void compute_padre_hijos(int x){
for (int y:conexiones[x]){
if (y!=padre[x]){
hijos[x].push_back(y);
padre[y]=x;
compute_padre_hijos(y);
}
}
}
void assign_hint1(int ind, int hint){
for (int i=10;i>=1;i--){
setHint(ind+1,i,hint%2);
hint/=2;
}
}
void assign_hint2(int ind, int hint){
for (int i=20;i>=11;i--){
setHint(ind+1,i,hint%2);
hint/=2;
}
}
void assignHints(int subtask, int n, int A[], int B[]) {
setHintLen(20);
conexiones=vvi(n);
for (int i=1;i<=n-1;i++){
conexiones[A[i]-1].push_back(B[i]-1);
conexiones[B[i]-1].push_back(A[i]-1);
}
padre=vi(n);
hijos=vvi(n);
padre[0]=-1;
compute_padre_hijos(0);
for (int i=0;i<n;i++) sort(hijos[i].begin(),hijos[i].end());
assign_hint1(0,1001);
assign_hint2(0,hijos[0][0]);
for (int i=1;i<n;i++){
if (hijos[i].size()){ //ponemos padre y primer hijo
//cerr << i << ": " << padre[i] << ' ' << hijos[i][0] << '\n';
assign_hint1(i,padre[i]);
assign_hint2(i,hijos[i][0]);
}
else{ //subimos hasta que encontramos un nuevo fork a la derecha
int ant=i;
int ac=padre[i];
while (hijos[ac][hijos[ac].size()-1]==ant && ac!=0){
ant=ac;
ac=padre[ac];
}
////cerr << i << ' ' << ac << ' ' << hijos[ac][hijos[ac].size()-1] << '\n';
if (ac==0 && hijos[ac][hijos[ac].size()-1]==ant){
//cerr<< i << ": 1023 1023" << '\n';
assign_hint1(i,1023);
assign_hint2(i,1023);
}
else{
assign_hint1(i,ac);
for (int j=0;j<hijos[ac].size();j++){
if (hijos[ac][j]==ant){
assign_hint2(i,hijos[ac][j+1]);
//cerr << i << ": " << ac << ' ' << hijos[ac][j+1] << '\n';
}
}
}
}
}
////cerr << "Assignment completed!\n";
}
///////////////////////////////////// Part 2
/**
int getLength ();
bool getHint (int j);
bool goTo(int x);
**/
int get_hint1(){
int sum=0;
for (int i=1;i<=10;i++){
sum*=2;
sum+=getHint(i);
}
return sum;
}
int get_hint2(){
int sum=0;
for (int i=11;i<=20;i++){
sum*=2;
sum+=getHint(i);
}
return sum;
}
void speedrun(int subtask, int N, int ac) {
ac--;
if (N==1) return;
//vamos al padre (1000 fallos)
if (ac!=0){
vi vecinos;
for (int i=0;i<N;i++){
if (goTo(i+1)){
vecinos.push_back(i);
goTo(ac+1);
}
}
if (vecinos.size()==1){
ac=vecinos[0];
goTo(ac+1);
}
else{
ac=get_hint1();
goTo(ac+1);
}
}
//subimos hasta 0
while (ac!=0){
////cerr << ac << ' ';
ac=get_hint1();
goTo(ac+1);
}
//bajamos hasta abajo
int ant;
int newac=get_hint2();
while (goTo(newac+1)){
ant=ac;
ac=newac;
newac=get_hint2();
}
int a=get_hint1();
int b=get_hint2();
//subimos hasta a, vamos a b y luego bajamos repetidamente(1000 fallos)
while (a!=1023){
////cerr << ac << ' ' << a << ' ' << b << '\n';
////cerr << get_hint1() << ' ' << get_hint2() << '\n';
goTo(ant+1);
ac=ant;
while (ac!=a){
ac=get_hint1();
goTo(ac+1);
}
ant=a;
ac=b;
goTo(b+1);
newac=get_hint2();
while (newac!=1023 && goTo(newac+1)){
////cerr << ac << ' ' << newac << '\n';
ant=ac;
ac=newac;
newac=get_hint2();
}
a=get_hint1();
b=get_hint2();
}
////cerr << "Speedrun completado!\n";
}
//////////////////////////////////////////////////////////////////////////////////////
Compilation message
speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:97:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int j=0;j<hijos[ac].size();j++){
| ~^~~~~~~~~~~~~~~~~
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:213:13: warning: 'ant' may be used uninitialized in this function [-Wmaybe-uninitialized]
213 | goTo(ant+1);
| ~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
189 ms |
672 KB |
Output is correct |
| 2 |
Correct |
161 ms |
804 KB |
Output is correct |
| 3 |
Correct |
189 ms |
672 KB |
Output is correct |
| 4 |
Correct |
188 ms |
688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
672 KB |
Output is correct |
| 2 |
Correct |
172 ms |
680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
848 KB |
Output is correct |
| 2 |
Correct |
175 ms |
800 KB |
Output is correct |
| 3 |
Correct |
188 ms |
812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
700 KB |
Output is correct |
| 2 |
Correct |
198 ms |
684 KB |
Output is correct |
| 3 |
Correct |
184 ms |
700 KB |
Output is correct |
| 4 |
Correct |
156 ms |
932 KB |
Output is correct |
| 5 |
Correct |
170 ms |
700 KB |
Output is correct |
| 6 |
Correct |
195 ms |
672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
704 KB |
Output is correct |
| 2 |
Correct |
141 ms |
672 KB |
Output is correct |
| 3 |
Correct |
148 ms |
680 KB |
Output is correct |
| 4 |
Correct |
177 ms |
800 KB |
Output is correct |
| 5 |
Correct |
155 ms |
704 KB |
Output is correct |
| 6 |
Correct |
178 ms |
752 KB |
Output is correct |
| 7 |
Correct |
201 ms |
668 KB |
Output is correct |
