//#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, f[N], cnt, deg[N], l[N] ;
vector<int> V[N];
/*
#include <iostream>
#include <map>
#include <set>
using namespace std;
static map<int, map<int, bool> > mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int> > neighbours;
void setHintLen(int l) {
if (length_set) {
cerr << "Cannot call setHintLen twice" << endl;
exit(0);
}
length = l;
length_set = true;
}
void setHint(int i, int j, bool b) {
if (!length_set) {
cerr << "Must call setHintLen before setHint" << endl;
exit(0);
}
mp[i][j] = b;
}
int getLength() { return length; }
bool getHint(int j) { return mp[current_node][j]; }
bool goTo(int x) {
if (neighbours[current_node].find(x) == neighbours[current_node].end()) {
++queries;
return false;
} else {
viz.insert(current_node = x);
cout << current_node <<" is current" << endl;
return true;
}
} */
void add(int a,int b) {
if(deg[a] == 1) {
for(int j = 1; j <= 10; j++) {
if(b & (1 << (j - 1))) setHint(a, j, 1);
}
return;
}
for(int j = 11; j <= 20; j++) {
if(b & (1 << (j - 11))) setHint(a, j, 1);
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
if(subtask == 1) {
setHintLen(N);
for(int i = 1; i < N; i++) {
setHint(A[i], B[i], 1);
setHint(B[i], A[i], 1);
}
}
else if(subtask == 2) {
setHintLen(20);
int x = -1;
for(int i = 1; i < N; i++) {
deg[A[i]]++; deg[B[i]]++;
if(deg[A[i]] == N - 2) x = A[i];
if(deg[B[i]] == N - 2) x = A[i];
}
for(int i = 1; i <= N; i++) {
if(i == x) continue;
for(int j = 1; j <= 10; j++) {
if((1 << (j - 1)) & x) setHint(i, j, 1);
}
}
}
else if(subtask == 3) {
setHintLen(20);
for(int i = 1; i < N; i++) {
deg[A[i]]++; deg[B[i]]++;
add(A[i], B[i]);
add(B[i], A[i]);
}
}
else if(subtask == 4) {
setHintLen(311);
vector<int> V[N + 5];
for(int i = 1; i < N; i++) {
V[A[i]].push_back(B[i]);
V[B[i]].push_back(A[i]);
}
for(int i = 1; i <= N; i++) {
if(V[i].size() <= 31) {
int cur = 1;
for(int j = 0; j< V[i].size(); j++) {
for(int k = 1;k <= 10; k++) {
if(V[i][j] & (1 << ( k - 1))) setHint(i, cur, 1);
cur++;
}
}
}
else setHint(i, 311, 1);
}
}
}
void dfs2(int u) {
int x = 0;
for(int j = 1; j <= 10; j++) x += (1 << (j - 1)) * getHint(j);
if(!x) {
for(int i = 1; i <= n; i++) {
if(i == u || f[i]) continue;
f[i] = 1; cnt++;
assert(goTo(i));
dfs2(i);
}
}
else if(cnt == n) return;
else goTo(x), dfs2(x);
}
void dfs(int u,int subtask, int par) {
if(subtask == 1){
for(int i = 1; i <= n; i++) {
if(getHint(i)) V[u].push_back(i);
}
}
else{
int x = 0;
for(int i = 1; i <= 10; i++) {
x += getHint(i) * ((1 << (i - 1)));
}
V[u].push_back(x);
x = 0;
for(int i = 11; i <= 20; i++) {
x += getHint(i) * ((1 << (i - 11)));
}
if(x) V[u].push_back(x);
}
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i] == par) continue;
goTo(V[u][i]);
dfs(V[u][i], subtask, u);
}
if(par != - 1)goTo(par);
}
void dfs4(int u, int par) {
if(!f[u]) cnt++;
f[u] = 1;
if(!getHint(311)) {
for(int i = 1; i <= 31; i++) {
int x = 0;
for(int j = 1; j <= 10; j++) {
if(getHint((i - 1) * 10 + j)) x += 1 << (j - 1);
}
if(x) V[u].push_back(x);
}
for(int i = 0; i < V[u].size(); i++) {
if(!f[V[u][i]]) goTo(V[u][i]), dfs4(V[u][i], u);
}
}
else {
int x = l[u] + 1;
for(int i = x; i <= n; i++) {
l[u]++;
int t = goTo(i);
if(par != i && t) {
dfs4(i, u);
}
}
}
if(cnt != n) goTo(par);
}
void speedrun(int subtask, int N, int start) { /* your solution here */
n = N;
if(subtask == 1) dfs(start, 1, -1);
if(subtask == 2) {
dfs2(start);
}
else if(subtask == 3) {
dfs(start, 3, -1);
}
else if(subtask == 4) {
dfs4(start, -1);
}
}
/*
int main() {
int N;
cin >> N;
int a[N], b[N];
for (int i = 1; i < N; ++i) {
cin >> a[i] >> b[i];
neighbours[a[i]].insert(b[i]);
neighbours[b[i]].insert(a[i]);
}
assignHints(4, N, a, b);
if (!length_set) {
cerr << "Must call setHintLen at least once" << endl;
exit(0);
}
cin >> current_node;
viz.insert(current_node);
speedrun(4, N, current_node);
if (viz.size() < N) {
cerr << "Haven't seen all nodes" << endl;
exit(0);
}
cerr << "OK; " << queries << " incorrect goto's" << endl;
return 0;
} */
Compilation message
speedrun.cpp: In function 'void add(int, int)':
speedrun.cpp:55:28: error: 'setHint' was not declared in this scope; did you mean 'setns'?
55 | if(b & (1 << (j - 1))) setHint(a, j, 1);
| ^~~~~~~
| setns
speedrun.cpp:60:28: error: 'setHint' was not declared in this scope; did you mean 'setns'?
60 | if(b & (1 << (j - 11))) setHint(a, j, 1);
| ^~~~~~~
| setns
speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:65:3: error: 'setHintLen' was not declared in this scope
65 | setHintLen(N);
| ^~~~~~~~~~
speedrun.cpp:67:4: error: 'setHint' was not declared in this scope; did you mean 'setns'?
67 | setHint(A[i], B[i], 1);
| ^~~~~~~
| setns
speedrun.cpp:72:3: error: 'setHintLen' was not declared in this scope
72 | setHintLen(20);
| ^~~~~~~~~~
speedrun.cpp:82:28: error: 'setHint' was not declared in this scope; did you mean 'setns'?
82 | if((1 << (j - 1)) & x) setHint(i, j, 1);
| ^~~~~~~
| setns
speedrun.cpp:87:3: error: 'setHintLen' was not declared in this scope
87 | setHintLen(20);
| ^~~~~~~~~~
speedrun.cpp:95:3: error: 'setHintLen' was not declared in this scope
95 | setHintLen(311);
| ^~~~~~~~~~
speedrun.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j = 0; j< V[i].size(); j++) {
| ~^~~~~~~~~~~~~
speedrun.cpp:106:37: error: 'setHint' was not declared in this scope; did you mean 'setns'?
106 | if(V[i][j] & (1 << ( k - 1))) setHint(i, cur, 1);
| ^~~~~~~
| setns
speedrun.cpp:112:9: error: 'setHint' was not declared in this scope; did you mean 'setns'?
112 | else setHint(i, 311, 1);
| ^~~~~~~
| setns
speedrun.cpp: In function 'void dfs2(int)':
speedrun.cpp:118:53: error: 'getHint' was not declared in this scope; did you mean 'getline'?
118 | for(int j = 1; j <= 10; j++) x += (1 << (j - 1)) * getHint(j);
| ^~~~~~~
| getline
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from speedrun.cpp:2:
speedrun.cpp:123:11: error: 'goTo' was not declared in this scope
123 | assert(goTo(i));
| ^~~~
speedrun.cpp:128:7: error: 'goTo' was not declared in this scope
128 | else goTo(x), dfs2(x);
| ^~~~
speedrun.cpp: In function 'void dfs(int, int, int)':
speedrun.cpp:133:7: error: 'getHint' was not declared in this scope; did you mean 'getline'?
133 | if(getHint(i)) V[u].push_back(i);
| ^~~~~~~
| getline
speedrun.cpp:139:9: error: 'getHint' was not declared in this scope; did you mean 'getline'?
139 | x += getHint(i) * ((1 << (i - 1)));
| ^~~~~~~
| getline
speedrun.cpp:144:9: error: 'getHint' was not declared in this scope; did you mean 'getline'?
144 | x += getHint(i) * ((1 << (i - 11)));
| ^~~~~~~
| getline
speedrun.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
speedrun.cpp:151:3: error: 'goTo' was not declared in this scope
151 | goTo(V[u][i]);
| ^~~~
speedrun.cpp:154:16: error: 'goTo' was not declared in this scope
154 | if(par != - 1)goTo(par);
| ^~~~
speedrun.cpp: In function 'void dfs4(int, int)':
speedrun.cpp:159:6: error: 'getHint' was not declared in this scope; did you mean 'getline'?
159 | if(!getHint(311)) {
| ^~~~~~~
| getline
speedrun.cpp:167:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
speedrun.cpp:168:20: error: 'goTo' was not declared in this scope
168 | if(!f[V[u][i]]) goTo(V[u][i]), dfs4(V[u][i], u);
| ^~~~
speedrun.cpp:175:12: error: 'goTo' was not declared in this scope
175 | int t = goTo(i);
| ^~~~
speedrun.cpp:181:15: error: 'goTo' was not declared in this scope
181 | if(cnt != n) goTo(par);
| ^~~~
