oj.uz

Submission #536917

# Submission time Handle Problem Language Result Execution time Memory
536917 2022-03-14T07:31:45 Z ecx Speedrun (RMI21_speedrun) C++17
27 / 100
 173 ms 760 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

namespace ST2 {

    void setbits(int N, int PA) {
        int R = PA;
        for (int i = 1; i <= 10; i++) {
            setHint(N, i, R&1);
            R = R>>1;
        }
    } 

    void st(int N, int A[], int B[]) {
        set<int> s;
        int rt = -1;
        for (int i = 1; i < N; i++) {
            if (s.find(A[i]) != s.end()) {
                rt = A[i];
                break;
            }
            s.insert(A[i]);

            if (s.find(B[i]) != s.end()) {
                rt = B[i];
                break;
            }
            s.insert(B[i]);
        }
        setHintLen(10);
        for (int i = 1; i < N+1; i++) {
            setbits(i, rt);
        }
    }
}

namespace ST3 {

    vector<vector<int> > ADL;
    vector<int> PA;
    vector<int> CH;
    void dp(int i, int pa) {
        PA[i]=pa;
        CH[pa]=i;
        for (int k : ADL[i]){ 
            if (k!=pa) dp(k, i);
        }
    }

    void setbits(int N, int PA, int CH) {
        int R = ((PA<<10) + CH);
        for (int i = 1; i <= 20; i++) {
            setHint(N, i, R&1);
            R = R>>1;
        }
    } 

    void st(int N, int A[], int B[]) {

        setHintLen(20);

        PA.assign(N+1, 0);
        CH.assign(N+1, 0);
        ADL.assign(N+1, vector<int>());
        for (int i = 1; i < N; i++) {
            ADL[A[i]].push_back(B[i]);
            ADL[B[i]].push_back(A[i]);
        }
        for (int i = 1; i <= N; i++) {
            if (ADL[i].size() == 1) {
                dp(i, 0);
                break;
            }
        }
        for (int i = 1; i <= N; i++) {
            setbits(i, PA[i], CH[i]);
        }

    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    if (subtask == 3) {
        ST3::st(N, A, B);
    }
    if (subtask == 2) {
        ST2::st(N, A, B);
    }
}

namespace SVST3 {

    int ch() {
        // bits 1 to 10, 1 is LSB, 10 is MSB
        int sol = 0;
        for (int i = 20; i > 0; i--) {
            sol *= 2;
            sol += getHint(i);
        }
        return sol - (sol>>10<<10);
    }

    int pa() {
        int sol = 0;
        for (int i = 20; i > 0; i--) {
            sol *= 2;
            sol += getHint(i);
        }
        return sol>>10;
    }

    void solve(int N, int start) {
        while (ch() > 0) goTo(ch());
        while (pa() > 0) goTo(pa());
    }

}

namespace SVST2 {

    int pa() {
        int sol = 0;
        for (int i = 10; i > 0; i--) {
            sol *= 2;
            sol += getHint(i);
        }
        return sol;
    }

    void solve(int N, int start) {
        int rt = pa();
        goTo(rt);
        for (int i = 1; i < N+1; i++) {
            goTo(i);
            goTo(rt);
        }
    }

}

void speedrun(int subtask, int N, int start) { /* your solution here */
    if (subtask == 3) SVST3::solve(N, start);
    if (subtask == 2) SVST2::solve(N, start);
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB setHintLen was never called
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 680 KB Output is correct
2 Correct 90 ms 684 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 672 KB Output is correct
2 Correct 150 ms 672 KB Output is correct
3 Correct 153 ms 760 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB setHintLen was never called
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB setHintLen was never called
2 Halted 0 ms 0 KB -