#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
#define MAX_N 1000
int n;
bitset <MAX_N + 1> viz;
vector <int> degree, last;
void setNumber(int poz, int x, int y)
{
while(y)
{
if(y & 1)
setHint(x, poz, 1);
y >>= 1;
poz --;
}
}
int getNumber(int poz, int node)
{
int start = poz - 10 + 1, nr = 0;
for(int i = start; i <= poz; i ++)
{
nr <<= 1;
nr += getHint(i);
}
return nr;
}
void dfs(int node, int parent)
{
viz[node] = 1;
for(int i = 1; i <= n; i ++)
if(getHint(i) && !viz[i])
{
goTo(i);
dfs(i, node);
}
goTo(parent);
}
void dfs2(int node, int parent)
{
viz[node] = 1;
for(int i = 1; i <= 2; i ++)
{
int next = getNumber(i * 10, node);
if(!viz[next] && next)
{
goTo(next);
dfs2(next, node);
}
}
goTo(parent);
}
void dfs3(int node, int parent)
{
viz[node] = 1;
if(getHint(316))
{
int sf = min(315, n);
for(int i = 1; i <= sf; i ++)
{
if(getHint(i) && !viz[i])
{
goTo(i);
dfs3(i, node);
}
}
for(int i = 316; i <= n; i ++)
{
if(goTo(i) && !viz[i])
{
goTo(i);
dfs3(i, node);
}
}
goTo(parent);
}
else
{
int next = 1; // orice diferit de 0 ca sa intre in while
for(int i = 1; i <= 31 && next; i ++)
{
next = getNumber(i * 10, node);
if(!viz[next] && next)
{
goTo(next);
dfs3(next, node);
}
}
goTo(parent);
}
}
void assign1(int a[], int b[])
{
setHintLen(n);
for(int i = 1; i < n; i ++)
{
setHint(a[i], b[i], 1);
setHint(b[i], a[i], 1);
}
}
void assign2(int a[], int b[])
{
if(n == 1)
return;
int center;
degree.resize(n + 1, 0);
setHintLen(10);
for(int i = 1; i < n; i ++)
{
degree[a[i]] ++;
degree[b[i]] ++;
if(degree[a[i]] == 1)
{
center = b[i];
setNumber(10 * degree[a[i]], a[i], b[i]);
}
if(degree[b[i]] == 1)
{
center = a[i];
setNumber(10 * degree[b[i]], b[i], a[i]);
}
}
for(int i = 1; i <= 10; i ++)
setHint(center, i, 0);
}
void assign3(int a[], int b[])
{
degree.resize(n + 1, 0);
setHintLen(20);
for(int i = 1; i < n; i ++)
{
degree[a[i]] ++;
degree[b[i]] ++;
setNumber(10 * degree[a[i]], a[i], b[i]);
setNumber(10 * degree[b[i]], b[i], a[i]);
}
}
void assign4(int a[], int b[])
{
degree.resize(n + 1, 0);
last.resize(n + 1, 0);
setHintLen(316);
for(int i = 1; i < n; i ++)
{
degree[a[i]] ++;
degree[b[i]] ++;
}
for(int i = 1; i < n; i ++)
{
if(degree[a[i]] <= 31)
{
last[a[i]] ++;
setNumber(10 * last[a[i]], a[i], b[i]);
}
else
{
setHint(a[i], 316, 1);
if(b[i] < 316)
setHint(a[i], b[i], 1);
}
if(degree[b[i]] <= 31)
{
last[b[i]] ++;
setNumber(10 * last[b[i]], b[i], a[i]);
}
else
{
setHint(b[i], 316, 1);
if(a[i] < 316)
setHint(b[i], a[i], 1);
}
}
}
void speedrun1(int root)
{
dfs(root, root);
}
void speedrun2(int root)
{
int nr = getNumber(10, root), center = root;
if(nr)
{
goTo(nr);
center = nr;
}
for(int i = 1; i <= n ; i ++)
{
if(i != center)
{
goTo(i);
goTo(center);
}
}
}
void speedrun3(int root)
{
dfs2(root, root);
}
void speedrun4(int root)
{
dfs3(root, root);
}
void assignHints(int subtask, int N, int A[], int B[])
{
n = N;
if(subtask == 1)
{
assign1(A, B);
return;
}
if(subtask == 2)
{
assign2(A, B);
return;
}
if(subtask == 3)
{
assign3(A, B);
return;
}
assign4(A, B);
}
void speedrun(int subtask, int N, int start)
{
n = N;
if(subtask == 1)
{
speedrun1(start);
return;
}
if(subtask == 2)
{
speedrun2(start);
return;
}
if(subtask == 3)
{
speedrun3(start);
return;
}
speedrun4(start);
}
Compilation message
speedrun.cpp: In function 'void assign2(int*, int*)':
speedrun.cpp:140:16: warning: 'center' may be used uninitialized in this function [-Wmaybe-uninitialized]
140 | setHint(center, i, 0);
| ~~~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
1560 KB |
Output is correct |
2 |
Correct |
20 ms |
1608 KB |
Output is correct |
3 |
Correct |
25 ms |
1416 KB |
Output is correct |
4 |
Correct |
26 ms |
1416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
1252 KB |
Output is correct |
2 |
Correct |
19 ms |
1000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
1200 KB |
Output is correct |
2 |
Correct |
53 ms |
1708 KB |
Output is correct |
3 |
Correct |
59 ms |
1196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
1584 KB |
Output is correct |
2 |
Correct |
45 ms |
1208 KB |
Output is correct |
3 |
Incorrect |
34 ms |
944 KB |
Solution didn't visit every node |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
The length is too large |
2 |
Halted |
0 ms |
0 KB |
- |