This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
const int MAXN = 1001;
vector<int> graf[MAXN];
vector<int> kolejnosc;
void dfset(int v, int last) {
kolejnosc.push_back(v);
int x = 1;
for (int j = 11; j <= 20; j++) {
if ((x & last) == x) {
setHint(v, j, 1);
}
else {
setHint(v, j, 0);
}
x *= 2;
}
for (auto syn: graf[v]) {
if (syn == last) {
continue;
}
dfset(syn, v);
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
setHintLen(20);
for (int i = 1; i < N; i++) {
// cout << "i = " << i << endl;
// cout << A[i] << " " << B[i] << endl;
graf[A[i]].push_back(B[i]);
graf[B[i]].push_back(A[i]);
}
// cout << "TU1" << endl;
dfset(1, 1);
// cout << "TU2" << endl;
rep(i, N - 1) {
int v = kolejnosc[i];
int w = kolejnosc[(i + 1) % N];
int x = 1;
for (int j = 1; j <= 10; j++) {
if ((x & w) == x) {
setHint(v, j, 1);
}
else {
setHint(v, j, 0);
}
x *= 2;
}
}
}
const int MAXN2 = 1001;
bool czy[MAXN2];
int dfs(int v, int last) {
czy[v] = true;
// cout << "v = " << v << endl;
int nowy = 0;
int x = 1;
for (int j = 1; j <= 10; j++) {
if (getHint(j)) {
nowy += x;
}
x *= 2;
}
// cout << "nowy = " << nowy << '\n';
if (czy[nowy]) {
goTo(last);
return nowy;
}
while (!czy[nowy] && goTo(nowy)) {
nowy = dfs(nowy, v);
}
goTo(last);
return nowy;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
getLength();
int v = start;
while (v != 1) {
int nekst = 0;
int x = 1;
for (int j = 11; j <= 20; j++) {
if (getHint(j)) {
nekst += x;
}
x *= 2;
}
goTo(nekst);
v = nekst;
}
dfs(1, 1);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |