/* Input format:
*
* N -- number of nodes
* a1 b1 -- edge 1
* ...
* a(N-1) b(N-1) -- edge N - 1
* x -- start node
*/
#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) == end(neighbours[current_node])) {
++queries;
return false;
} else {
viz.insert(current_node = x);
return true;
}
}
#include "speedrun.h"
#include <bits/stdc++.h>
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
if (subtask == 1){
setHintLen(N);
for (int x = 1; x < N; x++){
setHint(A[x], B[x], 1);
setHint(B[x], A[x], 1);
}
}
return;
}
bool vis[1007];
int n;
void dfs(int x, int p){
vis[x] = 1;
for (int y = 1; y <= n; y++){
if ( (!vis[y]) && getHint(y)){
goTo(y);
dfs(y, x);
goTo(x);
}
}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
n = N;
int length = getLength();
if (subtask == 1){
memset(vis, 0, sizeof(vis));
dfs(start, -1);
}
return;
}
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(1, N, a, b);
if (!length_set) {
cerr << "Must call setHintLen at least once" << endl;
exit(0);
}
cin >> current_node;
viz.insert(current_node);
speedrun(1, 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 speedrun(int, int, int)':
speedrun.cpp:85:6: warning: unused variable 'length' [-Wunused-variable]
85 | int length = getLength();
| ^~~~~~
speedrun.cpp: In function 'int main()':
speedrun.cpp:118:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
118 | if (viz.size() < N) {
| ~~~~~~~~~~~^~~
/usr/bin/ld: /tmp/ccHJzWC0.o: in function `setHintLen(int)':
stub.cpp:(.text+0xc0): multiple definition of `setHintLen(int)'; /tmp/ccIuZrI2.o:speedrun.cpp:(.text+0x420): first defined here
/usr/bin/ld: /tmp/ccHJzWC0.o: in function `setHint(int, int, bool)':
stub.cpp:(.text+0x150): multiple definition of `setHint(int, int, bool)'; /tmp/ccIuZrI2.o:speedrun.cpp:(.text+0x660): first defined here
/usr/bin/ld: /tmp/ccHJzWC0.o: in function `getLength()':
stub.cpp:(.text+0x200): multiple definition of `getLength()'; /tmp/ccIuZrI2.o:speedrun.cpp:(.text+0x4d0): first defined here
/usr/bin/ld: /tmp/ccHJzWC0.o: in function `getHint(int)':
stub.cpp:(.text+0x210): multiple definition of `getHint(int)'; /tmp/ccIuZrI2.o:speedrun.cpp:(.text+0x970): first defined here
/usr/bin/ld: /tmp/ccHJzWC0.o: in function `goTo(int)':
stub.cpp:(.text+0x420): multiple definition of `goTo(int)'; /tmp/ccIuZrI2.o:speedrun.cpp:(.text+0xb80): first defined here
/usr/bin/ld: /tmp/ccHJzWC0.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccIuZrI2.o:speedrun.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
