#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];
vector<int> x;
/*
#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 dfs(int u,int p) {
for(int i = 1; i <= 10; i++) {
if(p & (1 << (i - 1))) setHint(u, i, 1);
}
x.push_back(u);
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i] == p) continue;
dfs(V[u][i], u);
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
setHintLen(20);
for(int i = 1; i < N; i++) {
V[A[i]].push_back(B[i]);
V[B[i]].push_back(A[i]);
}
dfs(1, 0);
x.push_back(1);
for(int i = 0; i + 1 < x.size(); i++) {
for(int j = 11; j <= 20; j++) {
if(x[i + 1] & (1 << (j - 11))) setHint(x[i], j, 1);
}
}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
n = N;
int cnt = 0;
int w = 0;
while(n--) {
cnt++;
int x = 0;
for(int j = 11; j <= 20; j++) {
x += getHint(j) * (1 << (j - 11));
}
while(!goTo(x)) { w++; assert(w <= n);
int p = 0;
for(int j = 1; j <= 10; j++) {
p += getHint(j) * (1 << (j - 1));
}
goTo(p); start = p;
}
start = x;
}
}
/*
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 dfs(int, int)':
speedrun.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0; i + 1 < x.size(); i++) {
| ~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
988 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
996 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
94 ms |
1040 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
888 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
988 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
