oj.uz

Submission #857010

# Submission time Handle Problem Language Result Execution time Memory
857010 2023-10-05T08:17:17 Z iulia_morariu Speedrun (RMI21_speedrun) C++14
48 / 100
 106 ms 1848 KB 
#include <speedrun.h>
#include <bits/stdc++.h>

using namespace std;

void assignHints (int subtask , int N, int A[], int B[]){
    if(subtask == 1){
        setHintLen( N );

        for(int i = 1; i < N; i++){
            setHint( A[i], B[i], 1);
            setHint( B[i], A[i], 1);
        }
    }else if(subtask == 2){
        setHintLen(20);
        int vf[N + 1];
        for(int i = 1; i <= N; i++) vf[i] = 0;
        for(int i = 1; i < N; i++){
            vf[ A[i] ]++;
            vf[ B[i] ]++;
        }

        int nod = 0;
        for(int i = 1; i <= N; i++){
            if(vf[i] == N - 1) nod = i;
        }

        for(int i = 1; i < N; i++){
            for(int j = 0; j < 20; j++){
                bool set = 0;
                if( (nod & (1 << j)) ) set = 1;
                setHint(i, j + 1, set );
            }
        }
    }else{
        setHintLen(20);
        int vf[N + 1];
        for(int i = 0; i <= N; i++) vf[i] = 0;

        for(int i = 0; i < N; i++){
            vf[ A[i] ]++;
            vf[ B[i] ]++;
        }

        int capat = 0;
        for(int i = 0; i <= N; i++){
            if(vf[ i ] == 1) capat = i;
        }

        //cout << "Un capat e la " << capat << endl;

        int nd = capat;
        int last = capat;
        vf[capat]--;
        for(int i = 0; i < N; i++){
            int nx = 0;
            for(int j = 0; j < N; j++){
                if(A[j] == nd && B[j] != last){


                    for(int k = 1; k <= 10; k++){
                        bool set = 0;
                        if( (nd & (1 << (k - 1))) != 0) set = 1;
                        setHint( B[j], k, set );

                        set = 0;
                        if( (B[j] & (1 << (k - 1))) != 0 ) set = 1;
                        setHint( nd, k + 10, set );
                    }
                    last = nd;
                    nd = B[j];
                    break;

                }else if(B[j] == nd && A[j] != last){

                    for(int k = 1; k <= 10; k++){
                        bool set = 0;
                        if( (nd & (1 << (k - 1))) != 0) set = 1;
                        setHint( A[j], k, set );

                        set = 0;
                        if( (A[j] & (1 << (k - 1))) != 0 ) set = 1;
                        setHint( nd, k + 10, set );
                    }
                    last = nd;
                    nd = A[j];
                    break;

                }
            }
        }


    }
}

int vis[1001];
void dfs(int nd, int n){
    vis[nd] = 1;
    //cout << "Suntem la " << nd << endl;
    for(int i = 1; i <= n; i++){
        if( vis[i] || getHint(i) == 0 ) continue;
        //cout << "  -- > i = " << i << " getHint = " << getHint(i) << endl;
        goTo(i);
        vis[i] = 1;
        dfs(i, n);
        goTo(nd);
    }
}

void speedrun(int subtask , int N, int start ){
    if(subtask == 1){
        for(int i = 0; i <= N; i++) vis[i] = 0;
        vis[start] = 1;
        stack<int> s;
        s.push(start);

        dfs(start, N);
    }else if(subtask == 2){

        int nd = 0;
        for(int j = 0; j < 20; j++){
            nd += getHint(j + 1) * (1 << j);
        }

        if(nd != start){
            goTo( nd );
        }

        for(int i = 1; i <= N; i++){
            if(i == nd || i == start) continue;
            goTo(i);
            goTo(nd);
        }

    }else{

        int nod = start;
        while(true){
            int last = 0;
            for(int j = 1; j <= 10; j++){
                last += getHint(j) * (1 << (j - 1));
            }
            if(last == 0) break;
            goTo(last);
            nod = last;
        }

        //cout << "Am ajuns la nodul " << nod << endl;

        for(int i = 0; i < N - 1; i++){
            int next = 0;
            for(int j = 1; j <= 10; j++){
                next += getHint(j + 10) * (1 << (j - 1));
            }

            goTo(next);
        }


    }
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:56:17: warning: unused variable 'nx' [-Wunused-variable]
   56 |             int nx = 0;
      |                 ^~
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:138:13: warning: variable 'nod' set but not used [-Wunused-but-set-variable]
  138 |         int nod = start;
      |             ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1664 KB Output is correct
2 Correct 23 ms 1652 KB Output is correct
3 Correct 22 ms 1848 KB Output is correct
4 Correct 20 ms 1696 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1084 KB Output is correct
2 Correct 106 ms 1600 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1336 KB Output is correct
2 Correct 96 ms 1488 KB Output is correct
3 Correct 92 ms 1088 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 920 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 908 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -