oj.uz

답안 #535913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535913 2022-03-11T19:39:55 Z MeGustaElArroz23 Speedrun (RMI21_speedrun) C++14
100 / 100
 201 ms 932 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());


    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);
      |         ~~~~^~~~~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 672 KB Output is correct
2 Correct 172 ms 680 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 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

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 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

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 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