oj.uz

Submission #535904

# Submission time Handle Problem Language Result Execution time Memory
535904 2022-03-11T18:48:59 Z MeGustaElArroz23 Speedrun (RMI21_speedrun) C++17
0 / 100
 361 ms 796 KB 
///////////////////////////////////////////////////////////////////////////////////////


#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());

    /**
    vii aristas_que_sobran;
    for (int i=0;i<n;i++){
        for (int j=1;j<hijos[i].size();j++) aristas_que_sobran.push_back(pii{i,hijos[i][j]});
    }
    **/

    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
            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];
            }

            if (ac==0){
                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 << "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--;

    //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 newac=get_hint2();
    while (goTo(newac+1)){
        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';
        while (ac!=a){
            //cerr << ac << ' ' << a << '\n';
            ac=get_hint1();
            goTo(ac+1);
        }

        ac=b;
        goTo(b+1);

        int newac=get_hint2();
        while (goTo(newac+1)){
            cerr << ac << ' ' << newac << '\n';
            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:98:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for (int j=0;j<hijos[ac].size();j++){
      |                              ~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 672 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 229 ms 712 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 126 ms 796 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 361 ms 672 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 676 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -