#include "speedrun.h"
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int> > adj;
vector<pair<int,int> > hintss;
stack<int> s;
int root=1;
void dfs(int x, int e) {
if(adj[x].size()==1&&x!=root) {
hintss[x].first=s.top();
s.pop();
return;
}
if(adj[x][0]==e) {
hintss[x].first=adj[x][1];
} else {
hintss[x].first=adj[x][0];
}
for(int i=adj[x].size()-1;i>0;i--) {
if(adj[x][i]==e)
continue;
s.push(adj[x][i]);
}
for(auto b : adj[x]) {
if(b==e) continue;
hintss[b].second=x;
dfs(b,x);
}
}
void assignhints(int subtask, int N, int A[], int B[]) { /* your solution here */
adj.resize(N+1);
hintss.resize(N+1);
for(int i=0;i<N-1;i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
for(int i=1;i<=N;i++) {
if(adj[i].size()==1) {
root=i;
break;
}
}
dfs(root,-1);
setHintLen(20);
for(int i=1;i<=N;i++) {
for(int j=0;j<10;j++) {
if((hintss[i].first&(1<<j))!=0) {
setHint(i,j+1,1);
} else {
setHint(i,j+1,0);
}
}
for(int j=0;j<10;j++) {
if((hintss[i].second&(1<<j))!=0) {
setHint(i,j+11,1);
} else {
setHint(i,j+11,0);
}
}
}
}
int getparent(int x) {
int res=0;
for(int i=0;i<10;i++) {
if(getHint(i+11)) {
res|=(1<<i);
}
}
return res;
}
int getchild(int x) {
int res=0;
for(int i=0;i<10;i++) {
if(getHint(i+1)) {
res|=(1<<i);
}
}
return res;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
int sospeso=-1;
vector<bool> vis(N+1);
vector<int> childs(N+1);
vector<int> parents(N+1);
int nodo=start;
while(true) {
vis[nodo]=true;
childs[nodo]=getchild(nodo);
parents[nodo]=getparent(nodo);
if(vis[childs[nodo]]||childs[nodo]==0) {
if(sospeso!=-1) {
bool th = goTo(sospeso);
if(th) {
nodo = sospeso;
} else {
th = goTo(parents[nodo]);
nodo = parents[nodo];
}
} else if(!vis[parents[nodo]]&&parents[nodo]!=0) {
bool th = goTo(parents[nodo]);
nodo = parents[nodo];
} else {
break;
}
} else {
bool th = goTo(childs[nodo]);
if(th) {
nodo = childs[nodo];
} else {
sospeso=childs[nodo];
if(parents[nodo]==0)
break;
th = goTo(parents[nodo]);
nodo = parents[nodo];
}
}
}
}
Compilation message
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:104:22: warning: unused variable 'th' [-Wunused-variable]
104 | bool th = goTo(parents[nodo]);
| ^~
/usr/bin/ld: /tmp/ccEbPzKk.o: in function `main':
stub.cpp:(.text.startup+0x1d1): undefined reference to `assignHints(int, int, int*, int*)'
collect2: error: ld returned 1 exit status
