#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
#define MAX_N 1000
int n;
bitset <MAX_N + 1> viz;
vector <int> degree;
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 setNumber(int poz, int x, int y)
{
while(y)
{
if(y & 1)
setHint(x, poz, 1);
y >>= 1;
poz --;
}
}
//void assign2(int a[], int b[])
//{
// if(n == 1)
// continue;
//
// int center = 0;
// setHintLen(10);
//
// for(int i = 1; i <= 2; i ++)
// {
// idk.push_back(a[i]);
// idk.push_back(b[i]);
// }
//
// sort(idk.begin(), idk.end());
//
// bool ok = 0;
// for(int i = 1; i < 4 && !ok ; i ++)
// {
// if(v[i] == v[i - 1])
// center = v[i], ok = 1;
// }
//
// for(int i = 1; i < n; i ++)
// {
// if(a[i] == center)
// swap(a[i], b[i]);
// setNumber(a[i], b[i]);
// }
//}
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()
{
}
void assign4()
{
}
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 speedrun1(int root)
{
dfs(root, root);
}
int getNumber(int poz, int node)
{
int start = poz - 10 + 1, nr = 0;
for(int i = start; i <= poz; i ++)
{
nr += getHint(i);
nr <<= 1;
}
return nr;
}
void speedrun2(int root)
{
int nr = getNumber(10, root);
if(nr)
goTo(nr);
for(int i = 1; i <= n ; i ++)
{
if(i != nr && i != root)
{
goTo(i);
goTo(root);
}
}
}
void speedrun3(int root)
{
}
void assignHints(int subtask, int N, int A[], int B[])
{
n = N;
if(subtask == 1)
{
assign1(A, B);
return;
}
else if(subtask == 2)
{
assign2(A, B);
}
else if(subtask == 3)
{
assign3();
}
}
void speedrun(int subtask, int N, int start)
{
n = N;
if(subtask == 1)
{
speedrun1(start);
return;
}
else if(subtask == 2)
{
speedrun2(start);
return;
}
}
Compilation message
speedrun.cpp: In function 'void assign2(int*, int*)':
speedrun.cpp:91:16: warning: 'center' may be used uninitialized in this function [-Wmaybe-uninitialized]
91 | setHint(center, i, 0);
| ~~~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
1508 KB |
Output is correct |
2 |
Correct |
25 ms |
1228 KB |
Output is correct |
3 |
Correct |
23 ms |
1404 KB |
Output is correct |
4 |
Correct |
24 ms |
2332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
1160 KB |
Output is correct |
2 |
Incorrect |
19 ms |
768 KB |
Solution didn't visit every node |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
setHintLen was never called |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
setHintLen was never called |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
setHintLen was never called |
2 |
Halted |
0 ms |
0 KB |
- |