#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, 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, n1 & 1);
n1 >>= 1;
cidx--;
}
cidx = 19;
while (n2 > 0) {
setHint(i, cidx, 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);
}
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);
}
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);
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
796 KB |
Output is correct |
2 |
Correct |
37 ms |
800 KB |
Output is correct |
3 |
Correct |
39 ms |
740 KB |
Output is correct |
4 |
Correct |
44 ms |
800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Invalid bit index for setHint |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
336 KB |
Invalid bit index for setHint |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
setHintLen was never called |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
208 KB |
setHintLen was never called |
2 |
Halted |
0 ms |
0 KB |
- |