#include "speedrun.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
vector<ll>d[1007];
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){
int center = 0;
map<int, int> mp;
for(int i = 1; i < n; i++)
mp[a[i]]++, mp[b[i]]++;
int mx = 0;
for(auto i: mp)
if(i.second > mx){
mx = i.second;
center = i.first;
}
setHintLen(20);
for(int i = 1; i <= n; i++){
if(i == center)
continue;
for(int j = 0; j < 20; j++){
if((center >> j) % 2 != 0){
setHint(i, j + 1, 1);
}
}
}
}
else if(subtask == 3){
setHintLen(20);
for(int i = 1; i <= n; i++){
vector<int>nodes;
for(int j = 1; j < n; j++){
if(a[j] == i || b[j] == i){
int other = 0;
if(a[j] == i)
other = b[j];
else
other = a[j];
nodes.push_back(other);
}
}
if(!nodes.empty())
for(int j = 0; j < 10; j++)
if((nodes[0] >> j) % 2 != 0)
setHint(i, j + 1, 1);
if(nodes.size() >= 2){
for(int j = 10; j < 20; j++)
if((nodes[1] >> (j - 10)) % 2 != 0)
setHint(i, j + 1, 1);
}
}
}
else if(subtask == 4){
for(int i = 1; i < n; i++){
d[a[i]].push_back(b[i]);
d[b[i]].push_back(a[i]);
}
setHintLen(316);
int sz = sqrt(n);
for(int i = 1; i <= n; i++){
if(d[i].size() <= sz){ // the degree is less/equal than sqrt(n) => we can build an adjestancy list (10 bits per vertex)
int pos = 1;
for(auto x: d[i]){
for(int j = pos; j <= pos + 9; j++){
if((x >> (j - pos)) % 2 != 0)
setHint(i, j, 1);
}
pos += 10;
}
}
// else: leave it as it is, we're gonna check all N nodes using goTo later in speedrun
}
}
}
bool used[1007];
void dfs(int v, int par, int &n){
used[v] = true;
for(int i = 1; i <= n; i++){
if(!used[i] && getHint(i)){
goTo(i);
dfs(i, v, n);
}
}
if(par != -1)
goTo(par);
}
void dfs_3(int v, int par){
//cout << v << endl;
used[v] = true;
int v1 = 0, v2 = 0;
for(int i = 9; i >= 0; i--){
v1 *= 2;
if(getHint(i + 1))
v1++;
}
for(int i = 19; i >= 10; i--){
v2 *= 2;
if(getHint(i + 1))
v2++;
}
//cout << v1 << ' ' << v2 << endl;
if(!used[v1] && v1 != 0){
goTo(v1);
dfs_3(v1, v);
}
if(!used[v2] && v2 != 0){
goTo(v2);
dfs_3(v2, v);
}
if(par != -1)
goTo(par);
}
void dfs_4(ll v, ll par, int &n){
used[v] = true;
bool ok = false;
for(int i = 1; i <= 316; i++){
if(getHint(i))
ok = true;
}
if(!ok){ // there are no set bits, thus this node has degree > sqrt(n) and we can traverse over all N nodes using goTo (the amount of such nodes will not exceed sqrt(N) - why? idk, just seems logical, search for proof)
for(int i = 1; i <= n; i++){
if(goTo(i))
dfs_4(i, v, n);
}
}
else{ // this node has its adjactency list
for(int i = 1; i + 9 <= 316; i += 10){ // the start of new code
ll v2 = 0;
for(int j = 9; j >= 0; j--){
v2 *= 2;
if(getHint(i + j))
v2++;
}
if(v2 == 0) // there is an end in the list!
break;
if(!used[v2]){
goTo(v2);
dfs_4(v2, v, n);
}
}
}
if(par != -1) // go back, from where we've come
goTo(par);
}
void speedrun(int subtask, int n, int start) { /* your solution here */
if(subtask == 1){
dfs(start, -1, n);
}
else if(subtask == 2){
bool ok = false;
for(int i = 1; i <= 20; i++)
if(getHint(i))
ok = true;
int center = 0;
if(ok){
for(int j = 19; j >= 0; j--){
center *= 2;
if(getHint(j + 1)){
center++;
}
}
goTo(center);
}
else
center = start;
for(int i = 1; i <= n; i++){
if(i != start && i != center){
goTo(i);
goTo(center);
}
}
}
else if(subtask == 3){
dfs_3(start, -1);
}
else if(subtask == 4){
dfs_4(start, -1, n);
}
}
Compilation message
speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:101:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
101 | if(d[i].size() <= sz){ // the degree is less/equal than sqrt(n) => we can build an adjestancy list (10 bits per vertex)
| ~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
820 KB |
Output is correct |
| 2 |
Correct |
54 ms |
804 KB |
Output is correct |
| 3 |
Correct |
47 ms |
792 KB |
Output is correct |
| 4 |
Correct |
43 ms |
800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
672 KB |
Output is correct |
| 2 |
Correct |
37 ms |
688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
676 KB |
Output is correct |
| 2 |
Correct |
89 ms |
672 KB |
Output is correct |
| 3 |
Correct |
115 ms |
672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
672 KB |
Output is correct |
| 2 |
Correct |
95 ms |
672 KB |
Output is correct |
| 3 |
Correct |
327 ms |
672 KB |
Output is correct |
| 4 |
Correct |
78 ms |
748 KB |
Output is correct |
| 5 |
Correct |
90 ms |
676 KB |
Output is correct |
| 6 |
Correct |
61 ms |
672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
setHintLen was never called |
| 2 |
Halted |
0 ms |
0 KB |
- |
