oj.uz

Submission #536943

# Submission time Handle Problem Language Result Execution time Memory
536943 2022-03-14T07:57:51 Z ecx Speedrun (RMI21_speedrun) C++17
48 / 100
 189 ms 824 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

namespace ST1 {
    void st(int N, int A[], int B[]) {
        setHintLen(N);
        for (int i = 1; i < N; i++) {
            setHint(A[i], B[i], 1);
            setHint(B[i], A[i], 1);
        }
    }
}

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 == 1) ST1::st(N, A, B);
    if (subtask == 2) ST2::st(N, A, B);
    if (subtask == 3) ST3::st(N, A, B);
}

namespace SVST1 {

    int _gn;

    void dfs(int node, int pa) {
        for (int i = 1; i <= _gn; i++) {
            if (getHint(i) && (i!=pa)) {
                goTo(i);
                dfs(i, node);
                goTo(node);
            }
        }
    }

    void solve(int N, int start) {
        _gn = N;
        dfs(start, -1);
    }
}

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

}

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

}

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

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 804 KB Output is correct
2 Correct 59 ms 824 KB Output is correct
3 Correct 48 ms 792 KB Output is correct
4 Correct 54 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 672 KB Output is correct
2 Correct 97 ms 672 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 736 KB Output is correct
2 Correct 189 ms 736 KB Output is correct
3 Correct 94 ms 688 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 336 KB setHintLen was never called
2 Halted 0 ms 0 KB -