oj.uz

Submission #504718

# Submission time Handle Problem Language Result Execution time Memory
504718 2022-01-10T07:57:54 Z SanguineChameleon Speedrun (RMI21_speedrun) C++14
29 / 100
 260 ms 764 KB 
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;

void dfs1(int u, int N, bool flag[]) {
    for (int i = 1; i <= N; i++) {
        if (getHint(i) && !flag[i]) {
            flag[i] = true;
            goTo(i);
            dfs1(i, N, flag);
            goTo(u);
        }
    }
}

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

void ass2(int N, int A[], int B[]) {
    setHintLen(20);
    int cc[N + 1];
    fill_n(cc, N + 1, 0);
    for (int i = 1; i <= N - 1; i++) {
        cc[A[i]]++;
        cc[B[i]]++;
    }
    int p = -1;
    for (int i = 1; i <= N; i++) {
        if (cc[i] > 1) {
            p = i;
            break;
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < 20; j++) {
            setHint(i, j + 1, (p >> j) & 1);
        }
    }
}

void speed1(int N, int start) {
    bool flag[N + 1];
    fill_n(flag, N + 1, false);
    dfs1(start, N, flag);
}

void speed2(int N, int start) {
    int p = 0;
    for (int i = 0; i < 20; i++) {
        p |= (getHint(i + 1) << i);
    }
    goTo(p);
    for (int i = 1; i <= N; i++) {
        goTo(i);
        goTo(p);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    if (subtask == 1) {
        ass1(N, A, B);
    }
    if (subtask == 2) {
        ass2(N, A, B);
    }
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    if (subtask == 1) {
        speed1(N, start);
    }
    if (subtask == 2) {
        speed2(N, start);
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 760 KB Output is correct
2 Correct 45 ms 748 KB Output is correct
3 Correct 45 ms 764 KB Output is correct
4 Correct 41 ms 744 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 676 KB Output is correct
2 Correct 200 ms 660 KB Output is correct

Subtask #3
0.0 / 19.0

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

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 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 328 KB setHintLen was never called
2 Halted 0 ms 0 KB -