#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
const int ms = 1e3 + 20;
vector<int> p;
vector<int> adj[ms];
bool flag[ms];
int par[ms];
int nxt[ms];
void dfs1(int u, int N, bool flag[]) {
for (int i = 1; i <= N; i++) {
if (getHint(i) && !flag[i]) {
flag[i] = true;
goTo(i);
dfs1(i, N, flag);
goTo(u);
}
}
}
void dfs5(int u) {
p.push_back(u);
for (auto x: adj[u]) {
if (!flag[x]) {
par[x] = u;
flag[x] = true;
dfs5(x);
}
}
}
void ass1(int N, int A[], int B[]) {
setHintLen(N);
for (int i = 1; i <= N - 1; i++) {
setHint(A[i], B[i], 1);
setHint(B[i], A[i], 1);
}
}
void ass2(int N, int A[], int B[]) {
setHintLen(20);
int cc[N + 1];
fill_n(cc, N + 1, 0);
for (int i = 1; i <= N - 1; i++) {
cc[A[i]]++;
cc[B[i]]++;
}
int p = -1;
for (int i = 1; i <= N; i++) {
if (cc[i] > 1) {
p = i;
break;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 20; j++) {
setHint(i, j + 1, (p >> j) & 1);
}
}
}
void ass3(int N, int A[], int B[]) {
setHintLen(20);
vector<int> cc[N + 1];
for (int i = 1; i <= N - 1; i++) {
cc[A[i]].push_back(B[i]);
cc[B[i]].push_back(A[i]);
}
int p = -1;
for (int i = 1; i <= N; i++) {
if ((int)cc[i].size() == 1) {
p = i;
break;
}
}
deque<int> pt;
bool flag[N + 1];
fill_n(flag, N + 1, false);
flag[p] = true;
pt.push_back(p);
for (int i = 1; i <= N - 1; i++) {
for (auto x: cc[p]) {
if (!flag[x]) {
flag[x] = true;
p = x;
pt.push_back(x);
}
}
}
pt.push_front(0);
pt.push_back(0);
int lt, rt;
for (int i = 1; i <= N; i++) {
p = pt[i];
lt = pt[i - 1];
rt = pt[i + 1];
for (int j = 0; j < 10; j++) {
setHint(p, j + 1, (lt >> j) & 1);
setHint(p, j + 11, (rt >> j) & 1);
}
}
}
void ass5(int N, int A[], int B[]) {
setHintLen(20);
for (int i = 1; i <= N - 1; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
flag[1] = true;
dfs5(1);
for (int i = 0; i < (int)p.size() - 1; i++) {
nxt[p[i]] = p[i + 1];
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 10; j++) {
setHint(i, j + 1, (par[i] >> j) & 1);
setHint(i, j + 11, (nxt[i] >> j) & 1);
}
}
}
void speed1(int N, int start) {
bool flag[N + 1];
fill_n(flag, N + 1, false);
dfs1(start, N, flag);
}
void speed2(int N, int start) {
int p = 0;
for (int i = 0; i < 20; i++) {
p |= (getHint(i + 1) << i);
}
goTo(p);
for (int i = 1; i <= N; i++) {
goTo(i);
goTo(p);
}
}
void speed3(int N, int start) {
int lt, rt;
while (true) {
lt = 0;
rt = 0;
for (int i = 0; i < 10; i++) {
lt |= (getHint(i + 1) << i);
rt |= (getHint(i + 11) << i);
}
if (lt == 0) {
break;
}
goTo(lt);
}
while (true) {
lt = 0;
rt = 0;
for (int i = 0; i < 10; i++) {
lt |= (getHint(i + 1) << i);
rt |= (getHint(i + 11) << i);
}
if (rt == 0) {
break;
}
goTo(rt);
}
}
void speed5(int N, int start) {
int pa, nt;
while (true) {
pa = 0;
for (int i = 0; i < 10; i++) {
pa |= (getHint(i + 1) << i);
}
if (pa == 0) {
break;
}
goTo(pa);
}
while (true) {
nt = 0;
for (int i = 0; i < 10; i++) {
nt |= (getHint(i + 11) << i);
}
if (nt == 0) {
break;
}
while (true) {
pa = 0;
for (int i = 0; i < 10; i++) {
pa |= (getHint(i + 1) << i);
}
if (!goTo(nt)) {
goTo(pa);
}
else {
break;
}
}
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
if (subtask == 1) {
ass1(N, A, B);
}
if (subtask == 2) {
ass2(N, A, B);
}
if (subtask == 3) {
ass3(N, A, B);
}
if (subtask == 4 || subtask == 5) {
ass5(N, A, B);
}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
if (subtask == 1) {
speed1(N, start);
}
if (subtask == 2) {
speed2(N, start);
}
if (subtask == 3) {
speed3(N, start);
}
if (subtask == 4 || subtask == 5) {
speed5(N, start);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
716 KB |
Output is correct |
| 2 |
Correct |
31 ms |
804 KB |
Output is correct |
| 3 |
Correct |
48 ms |
792 KB |
Output is correct |
| 4 |
Correct |
48 ms |
808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
660 KB |
Output is correct |
| 2 |
Correct |
158 ms |
676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
660 KB |
Output is correct |
| 2 |
Correct |
107 ms |
728 KB |
Output is correct |
| 3 |
Correct |
168 ms |
672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
676 KB |
Output is correct |
| 2 |
Correct |
190 ms |
792 KB |
Output is correct |
| 3 |
Correct |
174 ms |
712 KB |
Output is correct |
| 4 |
Correct |
230 ms |
660 KB |
Output is correct |
| 5 |
Correct |
200 ms |
660 KB |
Output is correct |
| 6 |
Correct |
227 ms |
668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
804 KB |
Output is correct |
| 2 |
Correct |
206 ms |
696 KB |
Output is correct |
| 3 |
Correct |
228 ms |
700 KB |
Output is correct |
| 4 |
Correct |
191 ms |
660 KB |
Output is correct |
| 5 |
Correct |
117 ms |
724 KB |
Output is correct |
| 6 |
Correct |
232 ms |
656 KB |
Output is correct |
| 7 |
Correct |
210 ms |
676 KB |
Output is correct |
