#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
bool leaf[N+1];
bool visited[N+1];
long parent[N+1];
long first_val[N+1];
long second_val[N+1];
long depth[N+1];
stack<long> tovisit;
setHintLen(20);
vector<long> adjlist[N+1];
vector<long> leaves;
for (int i = 1;i<=N;i++){
leaf[i] = 1;
parent[i] = 0;
visited[i] = 0;
first_val[i] = -1;
second_val[i] = -1;
depth [i]= 0;
}
//setHintLen(N);
for(int i = 1;i<N;i++){
adjlist[A[i]].push_back(B[i]);
adjlist[B[i]].push_back(A[i]);
}
tovisit.push(1);
depth[1] = 1;
while(!tovisit.empty()){
long current = tovisit.top();
tovisit.pop();
if(visited[current]) continue;
visited[current]=1;
for (auto i:adjlist[current]){
if(!visited[i]){
depth[i] = depth[current] + 1;
leaf[current] = 0;
parent[i] = current;
tovisit.push(i);
}
}
}
for (int i = 1;i<=N;i++){
if (leaf[i]){
leaves.push_back(i);
}
}
for (auto green: leaves){
if (second_val[parent[green]]==-1) second_val[parent[green]] = green;
long current = parent[green];
while(current!=0){
first_val[current] = parent[current];
if (second_val[parent[current]]==-1) second_val[parent[current]] = current;
current = parent[current];
}
}
leaves.push_back(leaves[0]);
for (long i = 1;i<(long)leaves.size();i++){
long a = leaves[i-1];
long b = leaves[i];
if (a==b){
first_val[leaves[i-1]] = parent[leaves[i-1]];
second_val[leaves[i-1]] = leaves[i-1];
continue;
}
long b_low = 0;
while(depth[a]>depth[b]) a= parent[a];
while(depth[a]<depth[b]) {b= parent[b];b_low=b;}
while(a!=b){
a= parent[a];
b_low=b; b= parent[b];
}
first_val[leaves[i-1]] = b;
second_val[leaves[i-1]] = b_low;
}
for (long i = 1;i<=N;i++){
//cout<<i<<" "<<first_val[i]<<" "<<second_val[i]<<endl;
for (long j = 0;j<=9;j++) setHint(i,j+1,(first_val[i]>>j)&1);
for (long j = 0;j<=9;j++) setHint(i,j+11,(second_val[i]>>j)&1);
}
}
#define getData() first_val = 0;second_val = 0;for (long j = 0;j<=9;j++) first_val|=(long) getHint(j+1)<<j; for (long j = 0;j<=9;j++) second_val|=(long)getHint(j+11)<<j
void speedrun(int subtask, int N, int start) { /* your solution here */
long first_val = 0;
long second_val = 0;
for (int i = 1;i<=N;i++){
}
getData();
if (first_val!=0){
bool go_up = goTo(first_val);
//cout<<go_up<<endl;
long j = first_val;
if (!go_up) j = 0;
while (!go_up){
j++;
go_up = goTo(j);
}
getData();
getData();
//cout<<j<<endl;
while(first_val!=0){
goTo(first_val);
getData();
}
}
long current_node=1;
stack<long> path;
path.push(1);
while(goTo(second_val)){
current_node = second_val;
path.push(current_node);
getData();
}
long endpoint = current_node;
long lca = first_val;
long next_go = second_val;
while(path.top()!=lca){
path.pop();
goTo(path.top());
}
goTo(next_go);
path.push(next_go);
getData();
while(goTo(second_val)){
current_node = second_val;
path.push(current_node);
getData();
}
lca = first_val;
next_go = second_val;
while(path.top()!=endpoint){
while(path.top()!=lca){
path.pop();
goTo(path.top());
}
goTo(next_go);
path.push(next_go);
getData();
while(goTo(second_val)){
current_node = second_val;
path.push(current_node);
getData();
}
lca = first_val;
next_go = second_val;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
852 KB |
Solution didn't visit every node |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
1948 KB |
Output is correct |
| 2 |
Correct |
109 ms |
1444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
1624 KB |
Output is correct |
| 2 |
Correct |
104 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
90 ms |
1368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
1112 KB |
Solution didn't visit every node |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
1044 KB |
Solution didn't visit every node |
| 2 |
Halted |
0 ms |
0 KB |
- |
