#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
bool vis[1007];
int parset[1007];
vector<int> adj[1007];
vector<int> dorder[1007];
int n;
void dfs(int x, int p, int d){
vis[x] = 1;
parset[x] = p;
dorder[d].push_back(x);
for (auto y : adj[x]){
if (!vis[y]){
dfs(y, x, d+1);
}
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
setHintLen(20);
for (int x = 1; x < N; x++){
adj[A[x]].push_back(B[x]);
adj[B[x]].push_back(A[x]);
}
//let root be 1 always
dfs(1, 0, 0);
vector<int> inorder;
for (int x = 0; x <= N; x++){
for (auto y : dorder[x]){
inorder.push_back(y);
}
}
//data 1 is par
//data 2 is next
int next[N+1];
for (int x = 0; x < N-1; x++){
next[ inorder[x] ] = inorder[x+1];
}
next[inorder[N-1]] = inorder[0];
//encryption
for (int x = 1; x <= N; x++){
for (int z = 0; z <= 9; z++){
if (parset[x] & (1<<z)){
setHint(x, z+1, 1);
}
}
for (int z = 0; z <= 9; z++){
if (next[x] & (1<<z)){
setHint(x, z+11, 1);
}
}
}
return;
}
int par[1007];
int nextt[1007];
int cur;
#define WEIRD -23145
void setDetails(){
if (nextt[cur] != WEIRD) return;
par[cur] = 0; nextt[cur] = 0;
for (int z = 0; z <= 9; z++){
if (getHint(z+1)){
par[cur] += (1<<z);
}
}
for (int z = 0; z <= 9; z++){
if (getHint(z+11)){
nextt[cur] += (1<<z);
}
}
}
inline void assertGoTo(int x){
goTo(x);
}
inline void returnToRoot(){
setDetails();
int steps = 0;
while (cur != 1){
assertGoTo(par[cur]);
cur = par[cur];
setDetails();
steps++;
if (steps > 1500) assert(false);
}
}
vector<int> moves[1007];
inline void trace(int x){
returnToRoot();
for (auto z : moves[x]){
assertGoTo(z);
cur = z;
}
return;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
cur = start;
for (int x = 0; x < 1007; x++) par[x] = WEIRD;
for (int x = 0; x < 1007; x++) nextt[x] = WEIRD;
returnToRoot();
vector<int> inorder;
inorder.push_back(1);
int ptr = 0;
int nodeCount = 1;
int rounds = 0;
for (int z = 0; z < N-1; z++){
int nextnode = nextt[inorder.back()];
if (nextnode == 0) break;
trace(inorder[ptr]);
while (!goTo(nextnode)){
ptr++;
trace(inorder[ptr]);
}
nodeCount++;
inorder.push_back(nextnode);
cur = nextnode;
moves[cur] = moves[inorder[ptr]];
moves[cur].push_back(cur);
setDetails();
}
}
Compilation message
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:134:6: warning: unused variable 'rounds' [-Wunused-variable]
134 | int rounds = 0;
| ^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
1924 KB |
Output is correct |
2 |
Execution timed out |
3505 ms |
4784 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
1664 KB |
Output is correct |
2 |
Correct |
45 ms |
1692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3501 ms |
3956 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
760 ms |
2476 KB |
Output is correct |
2 |
Correct |
242 ms |
1952 KB |
Output is correct |
3 |
Correct |
103 ms |
2148 KB |
Output is correct |
4 |
Correct |
3117 ms |
3232 KB |
Output is correct |
5 |
Correct |
554 ms |
2304 KB |
Output is correct |
6 |
Correct |
65 ms |
1928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
543 ms |
2332 KB |
Output is correct |
2 |
Correct |
286 ms |
1732 KB |
Output is correct |
3 |
Correct |
110 ms |
1668 KB |
Output is correct |
4 |
Correct |
2780 ms |
3716 KB |
Output is correct |
5 |
Correct |
121 ms |
1932 KB |
Output is correct |
6 |
Correct |
580 ms |
2504 KB |
Output is correct |
7 |
Correct |
69 ms |
1448 KB |
Output is correct |