| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 923329 | shoryu386 | Speedrun (RMI21_speedrun) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "speedrun.h"
#include <bits/stdc++.h>
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];
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);
}
}
for (int z = 0; z <= 9; z++){
if (next[x] & (1<<z)){
setHint(x, z+10, 1);
}
}
}
return;
}
int par[1007];
int nextt[1007];
int cur;
void setDetails(){
par[cur] = 0; nextt[cur] = 0;
for (int z = 0; z <= 9; z++){
if (getHint(z)){
par[cur] += (1<<z);
}
}
for (int z = 0; z <= 9; z++){
if (getHint(z+10)){
nextt[cur] += (1<<z);
}
}
}
void assertGoTo(int x){
assert(goTo(x));
}
void returnToRoot(){
setDetails();
if (cur == 1){
return;
}
assertGoTo(par[cur]);
cur = par[cur];
returnToRoot();
}
vector<int> moves[1007];
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;
returnToRoot();
vector<int> inorder;
inorder.push_back(1);
int ptr = 0;
int nodeCount = 1;
while (nodeCount < N){
int nextnode = nextt[inorder.back()];
cerr << nextnode << ' ' << ptr << ' ' << inorder[ptr] << '\n';
trace(inorder[ptr]);
if (goTo(nextnode)){
nodeCount++;
inorder.push_back(nextnode);
cur = nextnode;
moves[cur] = moves[inorder[ptr]];
moves[cur].push_back(cur);
cerr << "To reach " << cur << ": ";
for (int z : moves[cur]) cerr << z << ' ';
cerr << '\n';
setDetails();
}
else{
ptr++;
}
}
}