oj.uz

Submission #536983

# Submission time Handle Problem Language Result Execution time Memory
536983 2022-03-14T08:37:41 Z squiddy Speedrun (RMI21_speedrun) C++17
40 / 100
 172 ms 812 KB 
#include "speedrun.h"
#include <bits/stdc++.h>

#define FOR(v, s, e) for (int v = s; v < e; v++)

using namespace std;

void assignHints(int subtask, int N, int A[], int B[]) { 
    if (subtask == 1) {
        setHintLen(N);
        FOR(i, 1, N) {
            setHint(A[i], B[i], 1);
            setHint(B[i], A[i], 1);
        }
    } else if (subtask == 2) {
        int centre = 0;
        if (N == 2) {
            centre = A[0];
        } else if (N > 2) {
            int x1 = A[1], x2 = B[1];
            int y1 = A[2], y2 = B[2];
            if (x1 == y1 || x1 == y2) {
                centre = x1;
            } else {
                centre = x2;
            }
        }
        int bits[20], i = 0;
        for (;centre > 0 && i < 20;i++) {
            bits[i] = centre & 1;
            centre >>= 1;
        }
        setHintLen(i + 1);
        FOR(nd, 1, N + 1) {
            FOR(j, 0, i) {
                setHint(nd, j + 1, bits[j]);
            }
        }
    } else if (subtask == 3) {
        // first 10, last 10
        setHintLen(20);
        vector<int> neighbours[N + 1];
        FOR(i, 1, N) {
            neighbours[A[i]].push_back(B[i]);
            neighbours[B[i]].push_back(A[i]);
        }
        FOR(i, 1, N + 1) {
            int n1 = neighbours[i][0];
            int n2 = neighbours[i].size() > 1 ? neighbours[i][1] : 0;
            int cidx = 9;
            while (n1 > 0) {
                setHint(i, cidx + 1, n1 & 1);
                n1 >>= 1;
                cidx--;
            }
            cidx = 19;
            while (n2 > 0) {
                setHint(i, cidx + 1, n2 & 1);
                n2 >>= 1;
                cidx--;
            }
        }
    }
}

vector<int> getPossible(int st, int n) {
    vector<int> possible;
    if (st == 1) {
        FOR(i, 0, n) {
            if (getHint(i + 1) == 1) {
                possible.push_back(i + 1);
            }
        }
    } else if (st == 3) {
        bitset<20> bits;
        FOR(i, 0, 20) {
            bits[i] = getHint(i + 1);
        }
        int n1 = 0;
        FOR(i, 0, 10) {
            n1 = (n1 << 1) + bits[i];
        }
        if (n1 != 0) possible.push_back(n1);
        int n2 = 0;
        FOR(i, 10, 20) {
            n2 = (n2 << 1) + bits[i];
        }
        if (n2 != 0) possible.push_back(n2);
    }
    return possible;
}

void dfs(int nd, int par, int n, int st) {
    vector<int> possible = getPossible(st, n);
    for(int node : possible) {
        if (node == par) continue;
        goTo(node);
        dfs(node, nd, n, st);
    }
    if (par != -1) goTo(par);
}


void speedrun(int subtask, int N, int start) {
    if (subtask == 1 || subtask == 3) {
        dfs(start, -1, N, subtask);
    } else if (subtask == 2) {
        int bits[20];
        FOR(i, 0, 20) {
            bits[i] = getHint(i + 1);
        }
        int centre = 0;
        FOR(i, 0, getLength()) {
            centre = (centre << 1) + bits[i];
        }
        if (start != centre) goTo(centre);
        FOR(i, 1, N + 1) {
            if (i != centre && i != start) {
                goTo(i); goTo(centre);
            }
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 796 KB Output is correct
2 Correct 45 ms 772 KB Output is correct
3 Correct 39 ms 764 KB Output is correct
4 Correct 51 ms 800 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 724 KB Invalid bit index for getHint
2 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 812 KB Output is correct
2 Correct 172 ms 728 KB Output is correct
3 Correct 153 ms 724 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 -