#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)
{
cerr << node << endl;
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(!viz[i] && goTo(i))
{
goTo(i);
dfs3(i, node);
}
}
goTo(parent);
}
else
{
int next = 1; // orice diferit de 0 ca sa intre in for
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:141:16: warning: 'center' may be used uninitialized in this function [-Wmaybe-uninitialized]
141 | setHint(center, i, 0);
| ~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1776 KB |
Output is correct |
| 2 |
Correct |
22 ms |
1264 KB |
Output is correct |
| 3 |
Correct |
23 ms |
1544 KB |
Output is correct |
| 4 |
Correct |
26 ms |
1844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
972 KB |
Output is correct |
| 2 |
Correct |
20 ms |
1140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
51 ms |
1864 KB |
Output is correct |
| 3 |
Correct |
50 ms |
1112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
1196 KB |
Output is correct |
| 2 |
Correct |
59 ms |
1896 KB |
Output is correct |
| 3 |
Correct |
89 ms |
1340 KB |
Output is correct |
| 4 |
Correct |
49 ms |
1360 KB |
Output is correct |
| 5 |
Correct |
57 ms |
1468 KB |
Output is correct |
| 6 |
Correct |
39 ms |
1452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
The length is too large |
| 2 |
Halted |
0 ms |
0 KB |
- |
